Theory of Computation at Columbia

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.

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
Rachel Cummings
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
Miranda Christ
Cryptography, Complexity, Algorithms
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
Jason Milionis
Complexity, Cryptography, Theoretical Neuroscience, Language
Complexity Theory, Quantum Computing
Complexity Theory, Learning Theory, Property Testing
Achille Nazaret
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