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
Seminars
- To receive weekly reminders and announcements of Theory & Algorithms seminars, please sign up for the theory seminar mailing list.
- Illinois Computer Science Speaker Series
With 23 New Faculty, Illinois CS Expands Prowess in Education, Research
News | September 1, 2020
Airport Security in a Post-COVID-19 World
News | May 2, 2020
As Fewer People Fly, Rate of Guns Found in Bags by TSA Jumps
News | April 27, 2020