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
• 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
• 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
• 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
• 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
• 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 (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
• 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
• 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
• 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