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

Algorithms, Fairness

Sam Deng

Machine Learning Theory, Trustworthy AI

Sam Fereidooni

Cognitive Neuroscience, Neurolinguistics, Natural Language Processing

Algebraic Techniques, Complexity Theory

Complexity Theory, Algorithms

Algorithmic Game Theory, Complexity Theory, Learning Theory

Jingwen Liu

Machine Learning Theory, Algorithms

Yasaman Mahdaviyeh

Algorithmic Game Theory, Blockchains, ML Theory, Complexity

Cryptography, Quantum Computing, Complexity Theory

Quantum Computing, Complexity Theory

Algorithmic Fairness, Algorithmic Privacy, Causal Inference

Large Language Models, Machine Learning, Algorithms

Hengjie Zhang

Approximation Algorithms, Data Structures

Algorithms

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
- Rutgers DIMACS
- Simons Algorithms and Geometry Collaboration
- Columbia's Year on Statistical ML

- COMS 4236: Introduction to Computational Complexity (F24)
- COMS 4281: Introduction to Quantum Computing (F24)
- COMS 6998: Computation and the Brain (F24)
- COMS 4232: Advanced Algorithms (S24)
- COMS 4773: Machine Learning Theory (S24)
- COMS 6261: Advanced Cryptography (S24)
- COMS 6998: Unconditional Lower Bounds and Derandomization (S24)
- COMS 4281: Introduction to Quantum Computing (F23)
- COMS 4261: Introduction to Cryptography (F23)
- COMS 4252: Computational Learning Theory (F23)
- COMS 4236: Introduction to Computational Complexity (F23)
- COMS 6998: Foundations of Data Privacy (F23)
- COMS 6998: Introduction to Property Testing (F23)
- COMS 6998: Algebraic Techniques in TCS (F23)
- COMS 6998: Algorithms for Massive Data (F23)
- COMS 6998: Reading the CS Classics (S23)
- COMS 4261: Introduction to Cryptography (S23)
- COMS 4232: Advanced Algorithms (S23)
- COMS 4236: Introduction to Computational Complexity (S23)
- COMS 4252: Computational Learning Theory (F22)
- COMS 4236: Introduction to Computational Complexity (F22)
- COMS 4995: Logic and Computability (F22)
- COMS 6998: Fair and Robust Algorithms (F22)
- COMS 6998: Fine Grained Complexity (F22)

- Dan Mitropolsky
- Binghui Peng
- Shivam Nadimpalli
- Clayton Sanford
- Tim Randolph
- William Brown
- Eric Neyman
- Sophie Huiberts
- Jaroslaw Blasiok
- Hamoon Mousavi
- Yaonan Jin
- Chengyu Lin
- Arpit Agarwal
- Zeta Avarikioti
- Emmanouil Vlatakis
- Kiran Vodrahalli
- Sandip Sinha
- 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