Our study of the theoretical foundations of computing spans algorithm design and analysis, complexity, optimization, cryptography, quantum 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.
Groups & Labs
Accessible Accordion
Areas of Expertise
Societal Impact
Results will appear in alphabetical order.
Cryptography Research Group
The Cryptography Group advances the foundations and applications of cryptography, including public-key and symmetric cryptography, obfuscation, attribute-based and functional encryption, secure multi-party computation, quantum cryptography and more.
Database Group
The UW Database Group does theoretical, systems and user-centered work in multimodal database management systems; generative AI and data management; complexity of query evaluation and optimization; scalable, interactive data visualization; and more.
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.
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.
Highlights
Allen School News
Cardinality estimation helps guide decisions on every aspect of query execution, but current methods often have large errors. To address this, Suciu introduced a more accurate and efficient cardinality estimator, LpBound, which provides a guaranteed upper bound on the query output size.
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.
Simons Insttute
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.