<h1>Umans, Christopher</h1> <h2>Book Chapter from <a href="https://authors.library.caltech.edu">CaltechAUTHORS</a></h2> <ul> <li>Umans, Christopher (2019) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191115-133902016">Fast generalized DFTs for all finite groups</a>; ISBN 978-1-7281-4952-3; 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS); 793-805; <a href="https://doi.org/10.1109/FOCS.2019.00052">10.1109/FOCS.2019.00052</a></li> <li>Hsu, Chloe Ching-Yun and Umans, Chris (2018) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20180410-153010180">A fast generalized DFT for finite groups of Lie type</a>; ISBN 978-1-6119-7503-1; Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms; 1047-1059; <a href="https://doi.org/10.48550/arXiv.1707.00349">10.48550/arXiv.1707.00349</a></li> <li>Umans, Chris (2017) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191118-123714214">FOCS 2017 Preface</a>; ISBN 978-1-5386-3464-6; 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS); xiii; <a href="https://doi.org/10.1109/FOCS.2017.5">10.1109/FOCS.2017.5</a></li> <li>Hsu, Chloe Ching-Yun and Umans, Chris (2017) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191115-144427087">On Multidimensional and Monotone k-SUM</a>; ISBN 9783959770460; 42nd International Symposium on Mathematical Foundations of Computer Science; Art. No. 50; <a href="https://doi.org/10.4230/LIPIcs.MFCS.2017.50">10.4230/LIPIcs.MFCS.2017.50</a></li> <li>Hoza, William M. and Umans, Chris (2017) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20170705-173204335">Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace</a>; ISBN 978-1-4503-4528-6; Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017; 629-640; <a href="https://doi.org/10.1145/3055399.3055414">10.1145/3055399.3055414</a></li> <li>Fefferman, Bill and Umans, Christopher (2016) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191118-141357870">On the Power of Quantum Fourier Sampling</a>; ISBN 9783959770194; 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016); Art. No. 1; <a href="https://doi.org/10.4230/LIPIcs.TQC.2016.1">10.4230/LIPIcs.TQC.2016.1</a></li> <li>Guo, Zeyu and Narayanan, Anand Kumar, el al. (2016) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191118-103356388">Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields</a>; ISBN 9783959770163; 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016); Art. No. 47; <a href="https://doi.org/10.4230/LIPIcs.MFCS.2016.47">10.4230/LIPIcs.MFCS.2016.47</a></li> <li>Cohn, Henry and Umans, Christopher (2013) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20160913-165513831">Fast matrix multiplication using coherent configurations</a>; ISBN 978-1-61197-251-1; Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms; 1074-1087; <a href="https://doi.org/10.1137/1.9781611973105.77">10.1137/1.9781611973105.77</a></li> <li>Alon, Noga and Shpilka, Amir, el al. (2012) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20130703-110037886">On Sunflowers and Matrix Multiplication</a>; ISBN 978-1-4673-1663-7; 27th Annual IEEE Conference on Computational Complexity (CCC); 214-223; <a href="https://doi.org/10.1109/CCC.2012.26">10.1109/CCC.2012.26</a></li> <li>Ta-Shma, Amnon and Umans, Christopher (2012) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191126-140535982">Better Condensers and New Extractors from Parvaresh-Vardy Codes</a>; ISBN 9780769547084; 2012 IEEE 27th Conference on Computational Complexity; 309-315; <a href="https://doi.org/10.1109/ccc.2012.25">10.1109/ccc.2012.25</a></li> <li>Fefferman, Bill and Shaltiel, Ronen, el al. (2012) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20120522-093532704">On beating the hybrid argument</a>; ISBN 978-1-4503-1115-1; Proceedings of the 3rd Innovations in Theoretical Computer Science Conference; 468-483; <a href="https://doi.org/10.1145/2090236.2090273">10.1145/2090236.2090273</a></li> <li>Buchfuhrer, Dave and Dughmi, Shaddin, el al. (2010) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20100824-073813316">Inapproximability for VCG-Based Combinatorial Auctions</a>; ISBN 978-0-898717-01-3; Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms; 518-536</li> <li>Agrawal, Manindra and Fortnow, Lance, el al. (2009) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191127-093701543">Algebraic Methods in Computational Complexity</a></li> <li>Agrawal, Manindra and Fortnow, Lance, el al. (2009) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191127-075729203">Algebraic Methods in Computational Complexity</a></li> <li>Kalyanaraman, Shankar and Umans, Christopher (2009) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20100707-095613286">The Complexity of Rationalizing Network Formation</a>; ISBN 978-1-4244-5116-6; 50th Annual IEEE Symposium on Foundations of Computer Science, 2009; 485-494; <a href="https://doi.org/10.1109/FOCS.2009.48">10.1109/FOCS.2009.48</a></li> <li>Kalyanaraman, Shankar and Umans, Christopher (2008) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191126-155702845">The Complexity of Rationalizing Matchings</a>; ISBN 978-3-540-92181-3; Algorithms and Computation; 171-182; <a href="https://doi.org/10.1007/978-3-540-92182-0_18">10.1007/978-3-540-92182-0_18</a></li> <li>Kedlaya, Kiran S. and Umans, Christopher (2008) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191126-160438923">Fast Modular Composition in any Characteristic</a>; ISBN 978-0-7695-3436-7; 2008 49th Annual IEEE Symposium on Foundations of Computer Science; 146-155; <a href="https://doi.org/10.1109/focs.2008.13">10.1109/focs.2008.13</a></li> <li>Kedlaya, Kiran S. and Umans, Christopher (2008) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191127-094213132">Fast polynomial factorization and modular composition</a></li> <li>Buchfuhrer, David and Umans, Christopher (2008) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20191112-131623581">The Complexity of Boolean Formula Minimization</a>; ISBN 978-3-540-70574-1; Automata, Languages and Programming; 24-35; <a href="https://doi.org/10.1007/978-3-540-70575-8_3">10.1007/978-3-540-70575-8_3</a></li> <li>Umans, Christopher (2008) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20170103-171822942">Fast polynomial factorization and modular composition in small characteristic</a>; ISBN 978-1-60558-047-0; STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing; 481-490; <a href="https://doi.org/10.1145/1374376.1374445">10.1145/1374376.1374445</a></li> <li>Kalyanaraman, Shankar and Umans, Christopher (2007) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20190828-102317126">Algorithms for Playing Games with Limited Randomness</a>; ISBN 9783540755197; Algorithms – ESA 2007; 323-334; <a href="https://doi.org/10.1007/978-3-540-75520-3_30">10.1007/978-3-540-75520-3_30</a></li> <li>Guruswami, Venkatesan and Umans, Christopher, el al. (2007) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20170426-160240908">Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes</a>; ISBN 0-7695-2780-9; Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07); 96-108; <a href="https://doi.org/10.1109/CCC.2007.38">10.1109/CCC.2007.38</a></li> <li>Shaltiel, Ronen and Umans, Christopher (2007) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20161219-151217993">Low-end uniform hardness vs. randomness tradeoffs for AM</a>; ISBN 978-1-59593-631-8; STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing; 430-439; <a href="https://doi.org/10.1145/1250790.1250854">10.1145/1250790.1250854</a></li> <li>Kalyanaraman, Shankar and Umans, Christopher (2006) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20190828-102318013">On Obtaining Pseudorandomness from Error-Correcting Codes</a>; ISBN 9783540499947; FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science; 105-116; <a href="https://doi.org/10.1007/11944836_12">10.1007/11944836_12</a></li> <li>Ta-Shma, Amnon and Umans, Christopher (2006) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20170427-151755097">Better lossless condensers through derandomized curve samplers</a>; ISBN 0-7695-2720-5; 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06); 177-186; <a href="https://doi.org/10.1109/FOCS.2006.18">10.1109/FOCS.2006.18</a></li> <li>Umans, Christopher (2006) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20170103-170341500">Group-theoretic algorithms for matrix multiplication</a>; ISBN 1-59593-276-3; ISSAC '06 Proceedings of the 2006 international symposium on Symbolic and algebraic computation; 5; <a href="https://doi.org/10.1145/1145768.1145772">10.1145/1145768.1145772</a></li> <li>Umans, Christopher (2006) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20200127-140148446">Optimization Problems in the Polynomial-Time Hierarchy</a>; ISBN 978-3-540-34021-8; Theory and Applications of Models of Computation; 345-355; <a href="https://doi.org/10.1007/11750321_33">10.1007/11750321_33</a></li> <li>Umans, Christopher (2005) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20200609-101642741">Reconstructive Dispersers and Hitting Set Generators</a>; ISBN 978-3-540-28239-6; Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques; 460-471; <a href="https://doi.org/10.1007/11538462_39">10.1007/11538462_39</a></li> <li>Cohn, Henry and Kleinberg, Robert, el al. (2005) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936">Group-theoretic Algorithms for Matrix Multiplication</a>; ISBN 0-7695-2468-0; 46th Annual IEEE Symposium on Foundations of Computer Science; 379-388; <a href="https://doi.org/10.1109/SFCS.2005.39">10.1109/SFCS.2005.39</a></li> <li>Cohn, Henry and Umans, Christopher (2003) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253">A Group-theoretic Approach to Fast Matrix Multiplication</a>; ISBN 0-7695-2040-5; 44th Annual IEEE Symposium on Foundations of Computer Science; 438-449; <a href="https://doi.org/10.1109/SFCS.2003.1238217">10.1109/SFCS.2003.1238217</a></li> <li>Umans, Christopher (2002) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20111110-081820059">Pseudo-Random Generators for All Hardnesses</a>; ISBN 0-7695-1468-5; 17th Annual Conference on Computational Complexity; 7-7; <a href="https://doi.org/10.1109/CCC.2002.1004326">10.1109/CCC.2002.1004326</a></li> <li>Shaltiel, Ronen and Umans, Christopher (2001) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20111121-092803461">Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator</a>; ISBN 0-7695-1390-5; 42nd Annual Symposium on Foundations of Computer Science; 648-657; <a href="https://doi.org/10.1109/SFCS.2001.959941">10.1109/SFCS.2001.959941</a></li> <li>Mossel, Elchanan and Umans, Christopher (2001) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20111118-115638180">On the Complexity of Approximating the VC dimension</a>; ISBN 0-7695-1054-X; 16th Annual IEEE Conference on Computational Complexity Proceedings; 220-225; <a href="https://doi.org/10.1109/CCC.2001.933889">10.1109/CCC.2001.933889</a></li> <li>Umans, Christopher (1999) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20120109-142652598">Hardness of Approximating Σ^(p)_(2) Minimization Problems</a>; ISBN 0-7695-0409-4; 40th Annual Symposium on Foundations of Computer Science; 465-474; <a href="https://doi.org/10.1109/SFFCS.1999.814619">10.1109/SFFCS.1999.814619</a></li> <li>Umans, Christopher (1998) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20120119-070934161">The Minimum Equivalent DNF Problem and Shortest Implicants</a>; ISBN 0-8186-9172-7; 39th Annual Symposium on Foundations of Computer Science; 556-563; <a href="https://doi.org/10.1109/SFCS.1998.743506">10.1109/SFCS.1998.743506</a></li> <li>Umans, Christopher and Lenhart, William (1997) <a href="https://resolver.caltech.edu/CaltechAUTHORS:20120126-092849476">Hamiltonian cycles in solid grid graphs</a>; ISBN 0-8186-8197-7; 38th Annual Symposium on Foundations of Computer Science: Proceedings; 496-505; <a href="https://doi.org/10.1109/SFCS.1997.646138">10.1109/SFCS.1997.646138</a></li> </ul>