Umans, Christopher

Combined from CaltechAUTHORS

• Umans, Christopher M. (2024) Fast Generalized DFTs for All Finite Groups; SIAM Journal on Computing; FOCS19-398-FOCS19-419; 10.1137/20m1316342
• Blasiak, Jonah and Church, Thomas, et el. (2019) Which groups are amenable to proving exponent two for matrix multiplication?; 10.48550/arXiv.1712.02302
• Fefferman, Bill and Umans, Chris (2019) Pseudorandom generators and the BQP vs. PH problem; 10.48550/arXiv.1007.0305
• Hsu, Chloe Ching-Yun and Umans, Chris (2019) A New Algorithm for Fast Generalized DFTs; ACM Transactions on Algorithms; Vol. 16; No. 1; Art. No. 4; 10.1145/3301313
• 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
• Bläser, Markus and Kabanets, Valentine, et el. (2018) Algebraic Methods in Computational Complexity; Dagstuhl Reports; Vol. 8; No. 9; 133-153; 10.4230/DagRep.8.9.133
• 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
• Blasiak, Jonah and Church, Thomas, et el. (2017) On cap sets and the group-theoretic approach to matrix multiplication; Discrete Analysis; Vol. 2017; No. 3; 1-27; 10.19086/da.1245
• Kabanets, Valentine and Thierauf, Thomas, et el. (2016) Algebraic and Combinatorial Methods in Computational Complexity; Dagstuhl Reports; Vol. 6; No. 10; 13-32; 10.4230/DagRep.6.10.13
• 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, et el. (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
• Agrawal, Manindra and Kabanets, Valentine, et el. (2014) Algebra in Computational Complexity; Dagstuhl Reports; Vol. 4; No. 9; 85-105; 10.4230/DagRep.4.9.85
• Umans, Christopher (2014) Special Issue "Conference on Computational Complexity 2013" Guest editor's foreword; Computational Complexity; Vol. 23; No. 2; 147-149; 10.1007/s00037-014-0088-x
• Fefferman, Bill and Shaltiel, Ronen, et el. (2013) On Beating the Hybrid Argument; Theory of Computing; Vol. 9; No. 1; 809-843; 10.4086/toc.2013.v009a026
• Alon, Noga and Shpilka, Amir, et el. (2013) On sunflowers and matrix multiplication; Computational Complexity; Vol. 22; No. 2; 219-243; 10.1007/s00037-013-0060-1
• 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
• Immorlica, Nicole and Katz, Jonathan N., et el. (2012) Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009); SIAM Journal on Computing; Vol. 41; No. 6; 1591-1592; 10.1137/120973305
• Agrawal, Manindra and Thierauf, Thomas, et el. (2012) Algebraic and Combinatorial Methods in Computational Complexity; Dagstuhl Reports; Vol. 2; No. 10; 60-78; 10.4230/DagRep.2.10.60
• Alon, Noga and Shpilka, Amir, et el. (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, et el. (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
• Kedlaya, Kiran S. and Umans, Christopher (2011) Fast Polynomial Factorization and Modular Composition; SIAM Journal on Computing; Vol. 40; No. 6; 1767-1802; 10.1137/08073408X
• Alon, Noga and Shpilka, Amir, et el. (2011) On Sunflowers and Matrix Multiplication; Electronic Colloquium on Computational Complexity; Vol. 2011; Art. No. 67
• Buchfuhrer, David and Umans, Christopher (2011) The complexity of Boolean formula minimization; Journal of Computer and System Sciences; Vol. 77; No. 1; 142-153; 10.1016/j.jcss.2010.06.011
• Fefferman, Bill and Umans, Christopher, et el. (2010) On beating the hybrid argument; Electronic Colloquium on Computational Complexity; Vol. 2010; Art. No. 186
• Lee, James R. and Umans, Chris (2010) Special Section On Foundations of Computer Science; SIAM Journal on Computing; Vol. 39; No. 6; 2397-2397; 10.1137/smjcat000039000006002397000001
• Buchfuhrer, Dave and Dughmi, Shaddin, et el. (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; Electronic Colloquium on Computational Complexity; Vol. 2009; Art. No. 145
• Dick, Kevin and Umans, Christopher (2009) Improved inapproximability factors for some Σ^p₂ minimization problems; Electronic Colloquium on Computational Complexity; Vol. 2009; Art. No. 107
• 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, et el. (2009) Algebraic Methods in Computational Complexity
• Agrawal, Manindra and Fortnow, Lance, et el. (2009) Algebraic Methods in Computational Complexity
• Shaltiel, Ronen and Umans, Christopher (2009) Low-End Uniform Hardness versus Randomness Tradeoffs for AM; SIAM Journal on Computing; Vol. 39; No. 3; 1006-1037; 10.1137/070698348
• Umans, Christopher (2009) Reconstructive Dispersers and Hitting Set Generators; Algorithmica; Vol. 55; No. 1; 134-156; 10.1007/s00453-008-9266-z
• Buchfuhrer, David and Umans, Christopher (2009) Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms; Electronic Colloquium on Computational Complexity; Vol. 2009; Art. No. 68
• Guruswami, Venkatesan and Umans, Christopher, et el. (2009) Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes; Journal of the ACM; Vol. 56; No. 4; 20; 10.1145/1538902.1538904
• Asodi, Vera and Umans, Christopher (2009) The complexity of the matroid-greedoid partition problem; Theoretical Computer Science; Vol. 410; No. 8-10; 859-866; 10.1016/j.tcs.2008.11.019
• 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
• Fortnow, Lance and Impagliazzo, Russell, et el. (2008) On the Complexity of Succinct Zero-Sum Games; Computational Complexity; Vol. 17; No. 3; 353-376; 10.1007/s00037-008-0252-2
• 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 (2008) The Complexity of Rationalizing Matchings; Electronic Colloquium on Computational Complexity; Art. No. 21
• 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, et el. (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
• Shaltiel, Ronen and Umans, Christopher (2006) Pseudorandomness for Approximate Counting and Sampling; Computational Complexity; Vol. 15; No. 4; 298-341; 10.1007/s00037-007-0218-9
• 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
• Kalyanaraman, Shankar and Umans, Christopher (2006) On obtaining pseudorandomness from error-correcting codes; Electronic Colloquium on Computational Complexity; Vol. 2006; TR06-128
• 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 and Villa, Tiziano, et el. (2006) Complexity of two-level logic minimization; IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems; Vol. 25; No. 7; 1230-1246; 10.1109/TCAD.2005.855944
• 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
• Shaltiel, Ronen and Umans, Christopher (2005) Simple extractors for all min-entropies and a new pseudorandom generator; Journal of the ACM; Vol. 52; No. 2; 172-216; 10.1145/1059513.1059516
• 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 Kleinberg, Robert, et el. (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
• 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