Algorithms and Theory

Our research is grounded on the timeless and fundamental question of what can be automated by algorithms. We seek to understand the theoretical limits and applications of what computers can and cannot do, which computational tasks can be solved efficiently, which tasks are hard for computers to solve no matter how clever the programming or data, and how these notions interact with and advance science and society.

Much of our research is related to new kinds of computational settings beyond a single traditional computer: for example, computation with massively parallel computers, computation in large computer networks, quantum computing, and biological computing. At the core of our research is the design of algorithms that are trustworthy, reliable, secure, and protective of user privacy, even when run on computer systems that fail or are controlled by untrustworthy parties.

Rigorous mathematical proofs and formal methods play a key role in ensuring the correctness and robustness of our algorithms. Our work spans and interacts with frontier research on foundational mathematical domains such as algebra, geometry, logic, and stochastics; much of our research is also related to graphs, networks, and other combinatorial structures. A key methodological approach is to automate our own work and explore the limits of doing so; we combine machine learning with formal logical reasoning to automate algorithm design and analysis.