Umans, Christopher
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
