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 Student Seminar. We also have an Undergraduate Theory Learning Seminar that organizes student-run reading groups for undergraduates. 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.

We regularly communicate on two listservs, which you can join on the attached links: theory-read (for seminar talks that include faculty) and theory-phd (for student-centric things, including our student seminar).

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.

Algorithms, Algebra in Computation, Complexity Theory

Sublinear Algorithms, High-dimensional Geometry,
Machine Learning Theory

Algorithmic Game Theory, Complexity Theory

Privacy, Algorithmic Game Theory, Machine Learning Theory, Fairness

Algorithmic Statistics, Machine Learning, Privacy

Computational Complexity, Cryptography

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

Complexity Theory, Communication Complexity, Fairness and Privacy

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

Quantum Computing, Complexity Theory, Cryptography, Information Theory

Algorithmic Game Theory, Algorithms

Algorithmic Game Theory, Learning Theory

Cryptography, Complexity, Algorithms

Sam Deng

Machine Learning Theory, Trustworthy AI

Yuval Efron

Sam Fereidooni

Cognitive Neuroscience, Neurolinguistics, Natural Language Processing

Dean Hirsch

Data Structures, Optimization

Randomness in Computation, Complexity Theory, Algorithmic Economics

Oliver Korten

Complexity Theory, Algorithms

Yuhao Li

Algorithmic Game Theory, Complexity Theory, Learning theory

Chengyu Lin

Yasaman Mahdaviyeh

Jason Milionis

Algorithmic Game Theory, Learning Theory, Complexity, Blockchains

Complexity, Cryptography, Theoretical Neuroscience, Language

Complexity Theory, Quantum Computing

Complexity Theory, Learning Theory, Property Testing

Algorithmic Game Theory, Algorithms, Complexity

Algorithms, Algorithmic Game Theory, Machine Learning, Networks

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

Cryptography, Data Structures

Hengjie Zhang

Approximation Algorithms, Data Structures

Algorithms, Complexity Theory

Cryptography, Information Security, Distributed-Ledger Technology

- Theory Lunch
- Student Learning Seminar
- Undergraduate Theory Learning Seminar
- 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 6998: Communication Complexity & Applications (S22)
- COMS 6998: Frontiers of Quantum Complexity & Cryptography (S22)
- COMS 6998: Quantum Computing: Theory & Practice (S22)
- COMS 4261: Introduction to Cryptography (S22)
- COMS 4236: Introduction to Computational Complexity (S22)
- COMS 4232: Advanced Algorithms (S22)
- COMS 4252: Computational Learning Theory (F21)
- COMS 4995: Foundations of Blockchains (F21)
- COMS 4995: Logic and Computability (F21)
- COMS 6995: Algebraic Techniques in TCS (F21)
- COMS 6995: Computation and the Brain (F21)
- COMS 4252: Computational Learning Theory (S21)
- COMS 4281: Introduction to Quantum Computing (S21)
- COMS 4995: Advanced Algorithms (S21)
- COMS 4236: Introduction to Computational Complexity (F20)
- COMS 4995: Information Theory in TCS (F20)
- COMS 4995: Foundations of Blockchains (F20)
- COMS 6995: Computation and the Brain (F20)
- COMS 4232: Advanced Algorithms (S20)
- COMS 4995: Incentives in Computer Science (S20)
- COMS 6261: Information-Theoretic Cryptography (S20)

- Peilin Zhong
- Kira Goldner
- Chin Ho Lee
- Arnold Flitser
- Marshall Ball
- Erik Waingarten
- Victor Lecomte
- 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