Our study of the theoretical foundations of computing spans algorithm design and analysis, complexity, optimization, cryptography, quantum computing and more.
We seek to answer fundamental and long-standing questions about the capabilities and limitations of our field, which has practical implications in economics, logistics, social welfare, transportation and many other real-world domains.
Research Groups & Labs
Theory of Computation Group
The Theory of Computation Group makes progress on fundamental problems in computer science, including algorithms, optimization, cryptography, quantum and more, to understand and expand the limits of the field.
Quantum Group
The Quantum Group does research on a variety of topics in quantum information and computation (primarily on the theory side), including quantum complexity theory, error-correction, cryptography, algorithms, and learning.
Allen School Faculty
Centers & Initiatives
The eScience Institute empowers researchers and students in all fields to answer fundamental questions through the use of large, complex, and noisy data. As the hub of data-intensive discovery on campus, we lead a community of innovators in the techniques, technologies, and best practices of data science and the fields that depend on them.
IFDS organizes its research around four core themes: complexity, robustness, closed-loop data science, and ethics and algorithms. By making concerted progress on these fundamental fronts, IFDS aims to lower several of the barriers to better understanding of data science methodology and to its improved effectiveness and wider relevance to application areas.
Highlights
Quanta Magazine
Oveis Gharan, a member of the Allen School’s Theory of Computation Group, was honored by the International Mathematical Union for his landmark contributions to the theory of algorithms.
Allen School News
In the award-winning paper, Nirkhe and his collaborators resolved a longstanding problem in quantum complexity theory by proving that quantum proofs are computationally more powerful than classical proofs.
Institute for Foundations of Data Science
The International Conference on Artificial Intelligence and Statistics (AISTATS) recognized Jamieson for his 2016 paper underpinning an approach to hyperparameter optimization that has been widely adopted within the machine learning community.