My research interests are in theoretical computer science, especially complexity theory. Specifically, I am interested in derandomization, explicit constructions, hardness of approximation, algorithms, and graph theory.
All online papers
My Ph.D. thesis: Approximability and Completeness in the Polynomial Hierarchy. U.C. Berkeley. 2000.
Theory:
K. Kedlaya and C. Umans. Fast modular composition in any characteristic. Manuscript, April 2008. To appear in FOCS 2008.
V. Asodi and C. Umans. The complexity of the matroid-greedoid partition problem. Manuscript, February 2008.
S. Kalyanaraman and C. Umans. The complexity of rationalizing matchings. Manuscript, February 2008.
D. Buchfuhrer and C. Umans. The complexity of Boolean formula minimization. Updated February 2008. Proceedings of Automata, Languages and Programming, 35th International Colloquium, (ICALP). p. 24-35. 2008. Won the Track A Best Paper Award.
C. Umans. Fast polynomial factorization and modular composition in small characteristic. Updated November 2007. Proceedings of the 40th Annual Symposium on Theory of Computing (STOC). pages 481-490. 2008. Invited to the STOC 2008 special issue of SICOMP.
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. Invited to STOC 2007 special issue of SICOMP. Full version (revised 5/8/2008).
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).
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. Invited to Algorithmica RANDOM 2005 Special Issue. Full version (revised 11/28/2006).
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
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]