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 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
Chengyu Lin
Dan Mitropolsky
Complexity, Cryptography, Theoretical Neuroscience, Language
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