Chris Umans
Christopher Umans | |
---|---|
Nationality | American |
Alma mater | Williams College, University of California, Berkeley |
Known for | Computational complexity, Algorithms, Hardness of approximation, Matrix Multiplication |
Scientific career | |
Fields | Computer Science |
Institutions | California Institute of Technology |
Doctoral advisor | Christos Papadimitriou |
Christopher Umans is a professor of Computer Science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, computational complexity, , and hardness of approximation.
Academic biography[]
Umans studied at Williams College, where he completed a BA degree in Mathematics and Computer Science in 1996. He then received a PhD in Computer Science from University of California, Berkeley in 2000 under Christos Papadimitriou. Following his PhD, he was a postdoctoral researcher at Microsoft Research until joining Caltech in 2002.
Research[]
Umans' research centers broadly around algorithms and complexity. He has made notable contributions to varied areas within this space including random number generation, expanders, and algorithms for matrix multiplication. A notable example is his work on developing a group theoretic approach for matrix multiplication.[1]
In 2008, Umans and his student Dave Buchfuhrer settled a 1979 conjecture on the complexity of unbounded Boolean formula minimization; the result won a best paper award at ICALP. [2]
Awards and honors[]
Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan Fellowship in 2005.[3] Additionally, his work has received "Best Paper" awards at the International Conference on Automata, Languages, and Programming (ICALP) and the IEEE Conference on Computational Complexity (CCC).
References[]
- ^ Cohn, H.; Umans, C. (2003), "A group-theoretic approach to fast matrix multiplication", 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pp. 438–449, arXiv:math/0307321, doi:10.1109/SFCS.2003.1238217, ISBN 978-0-7695-2040-7
- ^ Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization". Journal of Computer and System Sciences (JCSS). 77 (1): 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "The Complexity of Boolean Formula Minimization" (PDF). In Luca Aceto; Ivan Damgård; et al. (eds.). Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I. Lecture Notes in Computer Science (LNCS) 5125. Berlin / Heidelberg, Germany: Springer-Verlag. pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. This won the Best Paper Award in Track A "Algorithms, Automata, Complexity and Games".
- ^ Sloan Fellows
External links[]
- Living people
- California Institute of Technology faculty
- Theoretical computer scientists