Umans, Christopher

Book Chapter from CaltechAUTHORS

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