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.
Faculty Members
Faculty
Faculty
Faculty
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.
MEM-C is a NSF Materials Research Science and Engineering Center that integrates materials innovations with theory and computation to advance spin-photonic nanostructures and elastic layered quantum materials, aided by an “AI Core” that integrates artificial intelligence-driven materials discovery.
Highlights
Allen School News
Deeds introduced partition constraints, a new approach for making conjunctive query executions more efficient. He presented the research at the 28th International Conference on Database Theory (ICDT), earning both the Best Student Paper and Best Paper Awards.
Breakthrough Prize Foundation
Tang, who earned her Ph.D. as a member of the Allen School’s Theory group, received the 2025 Maryam Mirzakhani New Frontiers Prize for her work on classical analogs of quantum algorithms for machine learning and linear algebra, and quantum machine learning on quantum data.
Allen School News
Oveis Gharan, a member of the Allen School’s Theory group, and Ph.D. alumnus Kuikui Liu, now a professor at MIT, are among a team of researchers that received this year’s Held Prize from the National Academy of Sciences for introducing a new method for counting the bases of matroids.