The Theory of Computation group is a part of the Department of Computer Science in the Columbia School of Engineering and Applied Sciences.

We research the fundamental capabilities and limitations of efficient computation. In addition, we use computation as a lens to gain deeper insights into problems from the natural, social, and engineering sciences. Our active research areas include algorithmic game theory, complexity theory, cryptography, the design and analysis of algorithms, interactive computation and communication, theoretical neuroscience, property testing, the role of randomness in computation, sublinear and streaming algorithms, and the theoretical foundations of machine learning.

Our group is highly collaborative, both within Columbia and among peer institutions. We have a weekly Theory Lunch and a bi-weekly Student Seminar. Most graduate students have (at least) two advisors and collaborate with several professors and other students. Some of our faculty are cross-listed with the IEOR department and the Data Science Institute. We interact with the New York theory community at large through NYCAC, NYC Theory Day, NYC Crypto Day, and the Simons Collaboration on Algorithms and Geometry.

Our department and research group are growing, and we’re always looking for new members and collaborators. If you would like to join our group as a graduate student, please apply to the PhD program in Computer Science at Columbia. Please reach out to faculty directly for inquiries about postdoc positions.

Sublinear Algorithms, High-dimensional Geometry,
Machine Learning Theory

Algorithmic Game Theory, Complexity Theory

Algorithmic Statistics, Machine Learning, Privacy

Computational Complexity, Cryptography

Algorithms, Complexity, Algorithmic Game Theory, Evolution, The Brain, Learning

Algorithmic Game Theory, Algorithms, Cryptocurrencies, Microeconomics

Computational Complexity, Learning Theory, Randomness in Computation

Algorithms, Combinatorial Optimization, Network Algorithms, Scheduling

Information Theory, Communication Complexity, Data-Structure Lower Bounds

Algorithms, Complexity Theory, Combinatorial Optimization, Databases, Testing and Verification

Algorithms, Metric Embeddings, Approximation

Mechanism Design, Approximation Algorithms, Algorithmic Game Theory

Boolean Function Analysis, Complexity Theory, Cryptography

Algorithmic Game Theory, Algorithms, Complexity

Algorithms, Algorithmic Game Theory, Machine Learning, Networks

Complexity Theory, Data Structures, Learning Theory

Randomized Algorithms, Market & Mechanism Design, Graphs

Machine Learning Theory, Neural Networks, AI Fairness & Accountability

Negev Shekel-Nosatzki

Learning Theory, Data Structures, Information Theory, Sublinear Algorithms

Algorithmic Game Theory, Algorithms, Learning Theory

Theoretical Machine Learning, Algorithms

Algorithms, Complexity Theory, Property Testing

Cryptography, Data Structures

Hengjie Zhang

Approximation Algorithms, Data Structures

Sublinear Algorithms, High-dimensional Geometry,
Machine Learning Theory

Algorithms, Complexity Theory

Complexity Theory, Property Testing

Sublinear Algorithms

Cryptography, Information Security, Distributed-Ledger Technology

- Theory Lunch
- Student Learning Seminar
- Boolean Analysis Reading Group
- NYC Crypto Day and NYC Theory Day

- Columbia's Data Science Institute
- IEOR and Statistics at Columbia
- IAS School of Mathematics
- NYCAC 2019
- Rutgers DIMACS
- Simons Algorithms and Geometry Collaboration
- Columbia's Year on Statistical ML

- COMS 4231: Algorithms I (S20)
- COMS 4232: Advanced Algorithms (S20)
- COMS 4995: Incentives in Computer Science (S20)
- COMS 6261: Information-Theoretic Cryptography (S20)
- COMS 3261: Computer Science Theory (S20)
- COMS 6995: Computation and the Brain (F19)
- COMS 4231: Introduction to Cryptography (F19)
- COMS 4236: Introduction to Computational Complexity (F19)
- COMS 4995: Randomized Algorithms (F19)

- Kevin Shi
- Timothy Sun
- Ghada Almashaqbeh
- Lucas Kowalczyk
- Fabrice Benhamouda
- Sepideh Mahabadi
- Ilya Razenshteyn
- Alexander Golovnev
- Jinyu Xie
- Stuart Hadfield
- Clément Canonne
- Xiaorui Sun
- Dimitris Paparas
- Jon Ullman
- Fernando Krell
- Igor Carboni Oliveira
- Li-Yang Tan
- Iasonas Petras
- Dana Dachman-Soled
- Mariana Raykova
- Seung Geol Choi
- Dov Gordon
- Yevgeniy Vahlis
- Spyridon Antonakopoulos
- Ilias Diakonikolas
- Ragesh Jaiswal
- Emanuele Viola
- Homin K. Lee
- Andrew Wan
- Hoeteck Wee