My research interests are in theoretical computer science, especially computational complexity. Specifically, I am interested in derandomization, explicit constructions, algebraic complexity and algorithms, and hardness of approximation.
All online papers
My Ph.D. thesis: Approximability and Completeness in the Polynomial Hierarchy. U.C. Berkeley. 2000.
Theory:
J. Blasiak, H. Cohn, J.A. Grochow, K. Pratt, C. Umans. Matrix multiplication via matrix groups. Proceedings of ITCS 2023.
V. Bhargava, S. Ghosh, Z. Guo, M. Kumar, C. Umans. Fast Multivariate Multipoint Evaluation Over All Finite Fields. Proceedings of FOCS 2022. To appear in J. ACM, 2024.
C. Umans. Fast generalized DFTs for all finite groups. Manuscript. 2019. This version to appear in FOCS 2019. To appear in SICOMP special issue for FOCS 2019. Revised version, 2024.
J. Blasiak, T. Church, H. Cohn, J. Grochow and C. Umans. Which groups are amenable to proving exponent two for matrix multiplication? Manuscript. 2017.
C. Hsu and C. Umans. A new algorithm for fast generalized DFTs. Manuscript. 2017. Appeared in SODA 2018. Full version in ACM Transactions on Algorithms (TALG) 16 (1), 1-20, 2019. (special issue for SODA 2018).
C. Hsu and C. Umans. On multidimension and monotone k-sum. Proceedings of MFCS. 2017
W. Hoza and C. Umans. Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. Proceedings of the 49th Annual Symposium on Theory of Computing (STOC). pages 629-640. 2017. Full version invited to SICOMP Special Issue for STOC 2017.
J. Blasiak, T. Church, H. Cohn, J. Grochow, E. Naslund, W. Sawin, and C. Umans. On cap sets and the group-theoretic approach to matrix multiplication. Discrete Analysis 2017:3.
Z. Guo, A. Narayanan, and C. Umans. Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. Proceedings of MFCS. 47:1-47:14. 2016.
B. Fefferman and C. Umans. The Power of Quantum Fourier Sampling. TQC. 2016.
H. Cohn and C. Umans. Fast matrix multiplication using coherent configurations. Manuscript. July 2012. Updated 10/3/2012 (Section 6 is new). Proceedings of the SIAM International Conference on Discrete Algorithms (SODA). 2013.
A. Ta-Shma and C. Umans. Better condensers and new extractors from Parvaresh-Vardy codes. Manuscript. December 2011. Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC). p. 309-315. 2012. Official version here
N. Alon, A. Shpilka, and C. Umans. On sunflowers and matrix multiplication. Manuscript. April 2011. Revised version (updated 3/22/12). Proceedings of the 27th Annual IEEE Conference on Computational Complexity (CCC). p. 214-223. 2012. Official version here. Journal version in CCC2012 Special Issue of Computational Complexity 22(2):pages 219-243. 2013. Official version here
B. Fefferman, R. Shaltiel, C. Umans, and E. Viola. On beating the hybrid argument. Manuscript. December 2010. Proceedings of Innovations in Theoretical Computer Science (ITCS). p. 468-483. 2012. Conference version (updated 11/28/11). Official version here.
B. Fefferman and C. Umans. Pseudorandom generators and the BQP vs. PH problem. Manuscript. April 2010. Updated 12/21/2010. Appeared in QIP 2011 as a featured talk.
D. Buchfuhrer and C. Umans. Limits on the social welfare of maximal-in-range auction mechanisms. Manuscript. July 2009. Merged version: D. Buchfuhrer, S. Dughmi, H. Fu, R. Kleinberg, E. Mossel, C. Papadimitriou, M. Schapira, Y. Singer and C. Umans. Inapproximability for VCG-based combinatorial auctions. Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). pages 518-536. 2010. Official verson here.
S. Kalyanaraman and C. Umans. The complexity of rationalizing network formation. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 485-494. 2009. Official version here.
K. Kedlaya and C. Umans. Fast modular composition in any characteristic. Manuscript, updated August 2008. Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 146-155. 2008. Official version here. Invited to the FOCS 2008 special issue of SICOMP. Draft of full version (merged with STOC 2008 paper below) (updated 5/11/2009). Official version here.
V. Asodi and C. Umans. The complexity of the matroid-greedoid partition problem. (revised 11/17/08). Theoretical Computer Science 410(8-10). p. 859-866. 2009. Official version here.
S. Kalyanaraman and C. Umans. The complexity of rationalizing matchings. Manuscript, February 2008. Proceedings of Algorithms and Computation, 19th International Symposium (ISAAC) . pages 171-182. 2008. Official version here.
D. Buchfuhrer and C. Umans. The complexity of Boolean formula minimization. Updated April 2010. Proceedings of Automata, Languages and Programming, 35th International Colloquium, (ICALP). p. 24-35. 2008. Won the Track A Best Paper Award. Journal version in Special Issue Celebrating Karp's Kyoto Prize of JCSS 77(1):pages 142-153. 2011. Official version here
C. Umans. Fast polynomial factorization and modular composition in small characteristic. Updated March 2008. Proceedings of the 40th Annual Symposium on Theory of Computing (STOC). pages 481-490. 2008. Invited to the STOC 2008 special issue of SICOMP. Draft of full version (merged with FOCS 2008 paper above) (updated 5/11/2009).
S. Kalyanaraman and C. Umans. Algorithms for Playing Games with Limited Randomness. Proceedings of the 15th Annual European Symposium on Algorithms (ESA). pages 323-334. 2007.
R. Shaltiel and C. Umans. Low-end Hardness vs. Randomness Tradeoffs for AM. Proceedings of the 39th Annual Symposium on Theory of Computing (STOC). pages 430-439. 2007. Full version (revised 5/8/2008) in STOC 2007 Special Issue of SICOMP 39(3):pages 1006-1037. 2009. Official version here.
V. Guruswami, C. Umans, and S. Vadhan. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC). pages 96-108. 2007. Won the Best Paper Award. Originally Extractors and Condensers from Univariate Polynomials. ECCC TR06-134. Full version (revised 6/13/2008) in J. ACM 56(4). 2009. Official version here.
A. Ta-Shma and C. Umans. Better Lossless Condensers Through Derandomized Curve Samplers. Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 177-186. 2006.
S. Kalyanaraman and C. Umans. On Obtaining Pseudorandomness from Error-Correcting Codes. Proceedings of 26th Annual Foundations of Software Technology and Theoretical Computer Science (FSTTCS). LNCS #4337. pages 105-116. 2006.
C. Umans, T. Villa, and A. L. Sangiovanni-Vincentelli. Complexity of Two-Level Logic Minimization . IEEE Transactions on CAD 25(7):1230-1246. July 2006.
H. Cohn, R. Kleinberg, B. Szegedy, and C. Umans. Group-theoretic Algorithms for Matrix Multiplication. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 379-388. 2005. Invited to FOCS 2005 Special Issue. Slightly more detailed 12 page version.
C. Umans. Reconstructive Dispersers and Hitting Set Generators. 9th International Workshop on Randomization and Computation (RANDOM). pages 460-471. 2005. Official LNCS version is here. Full version (revised 11/28/2006) in RANDOM 2005 Special Issue of Algorithmica 55(1):pages 134-156. 2009. Official version here.
R. Shaltiel and C. Umans. Pseudorandomness for Approximate Counting and Sampling. Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity (CCC). pages 212-226. 2005. Won the Best Paper Award. Journal version (revised 10/4/2006) in CCC 05 Special Issue: Computational Complexity 15(4):pages 298-341. 2006. Official CC version is here. Also ECCC TR04-086.
L. Fortnow, R. Impagliazzo, V. Kabanets, and C. Umans. On the Complexity of Succinct Zero-Sum Games. Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity (CCC). pages 323-332. 2005. Also ECCC TR04-001. Journal version in Computational Complexity 17(3), 2008. Official version here.
H. Cohn and C. Umans. A Group-theoretic Approach to Fast Matrix Multiplication. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 438-449. 2003.
C. Umans. Pseudo-random Generators for All Hardnesses. Proceedings of the 34th Annual Symposium on Theory of Computing (STOC) . pages 627-634. 2002. Also abstract in Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity (CCC) . page 11. 2002. Journal version in STOC 02 Special Issue: JCSS 67(2): pages 419-440. 2003. Official JCSS version is here.
M. Schaefer and C. Umans. Completeness in the Polynomial-Time Hierarchy: a compendium (updated version). SIGACT News. guest Complexity Theory column. September 2002. Original version is here.
M. Schaefer and C. Umans. Completeness in the Polynomial-Time Hierarchy: Part II. SIGACT News. guest Complexity Theory column. December 2002. Original version is here.
R. Shaltiel and C. Umans. Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 648-657. 2001. Invited to FOCS 2001 Special Issue. Journal version (revised 12/8/2004) in JACM 52(2): pages 172-216. 2005. Official JACM version is here.
E. Mossel and C. Umans. On the Complexity of Approximating the VC Dimension. Proceedings of the Sixteenth Annual IEEE Conference on Computational Complexity (CCC). pages 220-225. 2001. Journal version in CCC 01 Special Issue: JCSS 65(4): pages 660-671. 2002. Official JCSS version is here.
A. Ta-Shma, C. Umans, and D. Zuckerman. Loss-less Condensers, Unbalanced Expanders, and Extractors.Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). pages 143-152. 2001. Journal version in Combinatorica 27(2):pages 213-240. 2007. Official Combinatorica version is here.
C. Umans. Hardness of Approximating Sigma2 Minimization Problems. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 465-474. 1999.
C. Umans. On the Complexity and Inapproximability of Shortest Implicant Problems. Proceedings of the 26th Annual Colloquium on Automata, Languages, and Programming (ICALP). pages 687-696. 1999. Most results appear in final form in the journal version of the FOCS 98 paper below.
C. Umans. The Minimum Equivalant DNF Problem and Shortest Implicants. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 556-563. 1998. Journal version in FOCS 1998 Special Issue: JCSS 63(4): pages 597-611. 2001. Official JCSS version is here.
W. Lenhart and C. Umans. Hamiltonian Cycles in Solid Grid Graphs. Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS). pages 496-505. 1997
C. Umans. An Algorithm for Finding Hamiltonian Cycles in Grid Graphs Without Holes. Undergraduate Thesis. Williams College. 1996.
Other works online:
P. Golland, R. Kikinis, M. Halle, C. Umans, W.E.L. Grimson, M.E. Shenton and J.A. Richolt. AnatomyBrowser: A Novel Approach to Visualization and Integration of Medical Information. Computer Assisted Surgery. Vol. 4. pages 129-143.1999.
A. Costello, C. Umans, and F. Wu. Online Backup and Restore. CS252 class project. U.C. Berkeley. Spring 1998.
J.E. Anderson, C. Umans, M. Halle, P. Golland, M. Jakab, R.W. McCarley, F. A. Jolesz, M.E. Shenton, and R. Kikinis. AnatomyBrowser: Java-based Interactive Teaching Tool for Learning Human Neuroanatomy. Radiological Society of North America Electronic Journal. Vol. 2. 1998.
C. Umans, M. Halle, and R. Kikinis. Multilayer Images for Interactive 3D Visualization on the World Wide Web. SPL Technical Report #51. September 1997.
[Home][Research][Teaching][Theory links][Other]