Chris Umans

Last updated
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, algebraic complexity, and hardness of approximation.

Contents

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] [2] [3] [4] [5] [6] [7]

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. [8]

Awards and honors

Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan Fellowship in 2005. [9] 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).

Related Research Articles

<span class="mw-page-title-main">Theoretical computer science</span> Subfield of computer science and mathematics

Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity.

ICALP, the International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe. Like most theoretical computer science conferences its contributions are strongly peer-reviewed. The articles have appeared in proceedings published by Springer in their Lecture Notes in Computer Science, but beginning in 2016 they are instead published by the Leibniz International Proceedings in Informatics.

<span class="mw-page-title-main">Christos Papadimitriou</span> Greek computer scientist (b. 1949)

Christos Charilaos Papadimitriou is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia University.

<span class="mw-page-title-main">Computational complexity of mathematical operations</span> Algorithmic runtime requirements for common math procedures

The following tables list the computational complexity of various algorithms for common mathematical operations.

Logic optimization is a process of finding an equivalent representation of the specified logic circuit under one or more specified constraints. This process is a part of a logic synthesis applied in digital electronics and integrated circuit design.

In abstract algebra, the triple product property is an identity satisfied in some groups.

In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n.

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.

In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and numerical algorithms for numerical linear algebra and optimization, so finding the fastest algorithm for matrix multiplication is of major practical relevance.

In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n.

<span class="mw-page-title-main">Ryan Williams (computer scientist)</span> Computer scientist

Richard Ryan Williams, known as Ryan Williams, is an American theoretical computer scientist working in computational complexity theory and algorithms.

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form

<span class="mw-page-title-main">Weighted automaton</span> Finite-state machine where edges carry weights

In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata.

<span class="mw-page-title-main">Henry Cohn</span> American mathematician

Henry Cohn is an American mathematician. He is a principal researcher at Microsoft Research and an adjunct professor at MIT. In collaboration with Abhinav Kumar, Stephen D. Miller, Danylo Radchenko, and Maryna Viazovska, he solved the sphere packing problem in 24 dimensions. In 2003, with Chris Umans he initiated a group-theoretic approach to matrix multiplication, and is a core contributor to its continued development with various coauthors.

<span class="mw-page-title-main">Virginia Vassilevska Williams</span> Theoretical computer scientist

Virginia Vassilevska Williams is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. She is notable for her breakthrough results in fast matrix multiplication, for her work on dynamic algorithms, and for helping to develop the field of fine-grained complexity.

In economics, a budget-additive valuation is a kind of a utility function. It corresponds to a person that, when given a set of items, evaluates them in the following way:

References

  1. ↑ 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, S2CID   5890100
  2. ↑ Cohn, Henry; Kleinberg, Robert; Szegedy, Balász; Umans, Christopher (2005). "Group-theoretic Algorithms for Matrix Multiplication". Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 379–388. doi:10.1109/SFCS.2005.39.
  3. ↑ Cohn, Henry; Umans, Christopher (2013). "Fast matrix multiplication using coherent configurations". Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. pp. 1074–1087. doi:10.1137/1.9781611973105.77.
  4. ↑ Alon, Noga; Shpilka, Amir; Umans, Christopher (2013). "On sunflowers and matrix multiplication". Computational Complexity. doi:10.1007/s00037-013-0060-1.
  5. ↑ Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Naslund, Eric; Sawin, William F.; Umans, Christopher (2017). "On cap sets and the group-theoretic approach to matrix multiplication". Discrete Analysis. doi:10.19086/da.1245.
  6. ↑ Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Umans, Christopher (2017). "Which groups are amenable to proving exponent two for matrix multiplication?". arXiv: 1712.02302 [math.GR].
  7. ↑ Blasiak, Jonah; Cohn, Henry; Grochow, Joshua A.; Pratt, Kevin; Umans, Christopher (2023). "Matrix Multiplication via Matrix Groups". 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 19:1-19:16. doi:10.4230/LIPIcs.ITCS.2023.19.
  8. ↑ 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). "Automata, Languages and Programming" (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. Vol. 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".
  9. ↑ Sloan Fellows
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.