skip to main content

Theory and Algorithms

Theoretical computer science develops efficient algorithms and explores fundamental barriers to efficient and secure computation. Advances in algorithms can provide dramatic performance gains, which are critically important as the era of Moore's Law—and its promise of ever-increasing processor speeds—draws to a close.

Our faculty develop algorithms to find optimal paths, trees, flows, clusters, and other important combinatorial structures in geometric and network data. For problems where computing the best possible solution is prohibitively expensive, we develop fast approximation algorithms to compute provably good solutions, and we explore the limits of what cannot even be approximated quickly. We develop algorithms that exploit geometric, algebraic, and topological properties of data that arise naturally in practice. Within cryptography, we develop protocols for secure multiparty computation and code obfuscation. In algorithmic game theory, we study the impact of strategic behavior among multiple agents. Our research, in addition to its fundamental importance, has many near-term applications in Computer Science and beyond.

Faculty & Affiliate Faculty

Geometry, Parallel Algorithms, Computational Biology

Computational Geometry, Algorithms, Data Structures

Combinatorial Optimization, Integer Programming, Probabilistic Methods and Analysis, Randomized Algorithms  

 Algorithms, Optimization

Applied Probability, Information Theory, Game Theory, Machine Learning, Quantum Information Theory

Combinatorial Optimization, Integer Linear Programming, Computational Biology

Computational Geometry and Topology, Algorithms

Pseudorandomness, Algebraic Computation, Computational Complexity

Algorithms, Game Theory, Fair Division

Algorithms for and Analysis of Networks and Distributed Systems

Computational Geometry, Geometric Approximation Algorithms

Optimization, Operations Research

Cryptography, Secure Computation, Zero-Knowledge, Differential Privacy

Algorithmic Game Theory, Mathematical Economics, Efficient Algorithms

Social Networks, Graph Algorithms, Applied Operations Research, Discrete Optimization

Cryptography, Distributed Algorithms

Machine Learning Theory

Model Checking, Logic, Cyberphysical Systems, Software, Security 

Graph Algorithms, Statistical Estimation, Heuristics for NP-Hard Optimization Problems, Experimental Algorithmics, Applications to Grand Challenges in Biology and Historical Linguistics

Machine Learning Theory, Operations Research, Combinatorial Optimization

Adjunct Faculty

Complexity Theory, Spectral Methods for Graph Algorithms 

Cryptography, Secure Multi-Party Computation 


Related News