Theoretical Computer Science

This field comprises two sub-fields: the theory of algorithms, which involves the design and analysis of computational procedures; and complexity theory, which involves efforts to prove that no efficient algorithms exist in certain cases, and which investigates the classification system for computational tasks. Time, memory, randomness and parallelism are typical measures of computational effort.

Theoretical computer science is a natural bridge between mathematics and computer science, and both fields have benefited from the connection. The field is very active, with exciting breakthroughs and intriguing challenges. The P =? NP problem is one of the seven of the Clay Millennium Problems. The recent polynomial time primality algorithm received a Clay Math research award.

MIT has been the leading center for theoretical computer science for several decades. A strong group of EECS Department faculty also works in this field and runs joint activities with the Mathematics faculty through CSAIL. The RSA cryptosystem and Akamai Technologies are two important success stories that were developed by Mathematics and EECS Department faculty.

Our group investigates active areas such as quantum computation, approximation algorithms, algorithms in number theory, distributed computing and complexity theory.

Department Members in This Field

Faculty

• Michel Goemans Algorithms, Combinatorics & Optimization
• Jonathan Kelner Theoretical Computer Science
• Tom Leighton Theoretical Computer Science, Combinatorics
• Dor Minzer
• Ankur Moitra Theoretical Computer Science, Machine Learning
• Elchanan Mossel Probability, Algorithms and Inference
• Peter Shor Quantum Computation, Quantum Information
• Michael Sipser Algorithms, Complexity Theory

Instructors & Postdocs

• Mitali Bafna Theoretical Computer Science
• Manik Dhar Combinatorics, Theoretical Computer Science
• Jason Gaitonde Algorithms, Learning Theory, Probability Theory, Networks
• Shivam Nadimpalli Analysis of Boolean Functions, High-Dimensional Geometry, Property Testing
• Alexander Poremba Quantum computation, cryptography
• Yihui Quek Quantum Computing, Complexity Theory, Quantum Noise and Error Correction
• Michael Simkin Probabilistic combinatorics, random graphs, and random processes
• Anirudh Sridhar Statistical inference, network cascades, graph algorithms, graph matching

Researchers & Visitors

• Ravi Boppana Combinatorics, Discrete Probability, Theoretical Computer Science

Graduate Students*

• Anna Brandenberger
• David Cui
• Andrey Khesin Quantum Computing
• Jonathan Lu
• Nitya Mani
• Janko Ondras
• Yuchong Pan
• Jonathan Rodriguez Figueroa
• Xinyu (Norah) Tan Quantum computing, quantum information, coding theory
• Neekon Vafa
• Shuo Wang Theoretical Computer Science, Combinatorics
• Lichen Zhang Theoretical computer science, machine learning and data science
• Kai Zhe Zheng

*Only a partial list of graduate students