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.
CS Faculty, Affiliated Faculty, and Their Research Interests
|Nancy M. Amato||Geometry, Parallel Algorithms, Computational Biology|
|Timothy Chan||Computational Geometry, Algorithms, Data Structures|
|Karthik Chandrasekaran, Industrial & Enterprise Systems Engineering||Combinatorial Optimization, Integer Programming, Probabilistic Methods and Analysis, Randomized Algorithms|
|Chandra Chekuri||Algorithms, Optimization|
|Mohammed El-Kebir||Combinatorial Optimization, Integer Linear Programming, Computational Biology|
|Jeff Erickson||Computational Geometry and Topology, Algorithms|
|Michael A. Forbes||Pseudorandomness, Algebraic Computation, Computational Complexity|
|Jugal Garg, Industrial & Enterprise Systems Engineering||Algorithms, Game Theory, Fair Division|
|Brighten Godfrey||Algorithms for and Analysis of Networks and Distributed Systems|
|Sariel Har-Peled||Computational Geometry, Geometric Approximation Algorithms|
|Sheldon Jacobson||Optimization, Operations Research|
|Negar Kiyavash, Electrical & Computer Engineering and Industrial & Enterprise Systems Engineering||Learning, Statistical Signal Processing, and Information Theory; Causality; Network Forensics|
|Dakshita Khurana||Cryptography, Secure Computation, Zero-Knowledge, Differential Privacy|
|Ruta Mehta||Algorithmic Game Theory, Mathematical Economics, Efficient Algorithms|
|Rakesh Nagi, Industrial & Enterprise Systems Engineering||Social Networks, Graph Algorithms, Applied Operations Research, Discrete Optimization|
|Ling Ren||Cryptography, Distributed Algorithms|
|Matus Telgarsky||Machine Learning Theory|
|Mahesh Viswanathan||Model Checking, Logic, Cyberphysical Systems, Software, Security|
|Tandy Warnow||Graph Algorithms, Statistical Estimation, Heuristics for NP-Hard Optimization Problems, Experimental Algorithmics, Applications to Grand Challenges in Biology and Historical Linguistics|
|Alexandra Kolla, University of Colorado at Boulder||Complexity Theory, Spectral Methods for Graph Algorithms|
|Manoj Prabhakaran, IIT Bombay||Cryptography, Secure Multi-Party Computation|
Related Theory and Algorithms Research Efforts and Groups
- Information Trust Institute (ITI) in the Coordinated Science Lab
- Carl R. Woese Institute for Genomic Biology (IGB)
- Theory and Algorithms Group
To receive weekly reminders and announcements of Theory & Algorithms seminars, please sign up for the theory-seminar mailing list.
Theory and Algorithms Research News
The Washington Post -- The Transportation Security Administration intercepted a record number of firearms at airport security checkpoints last year in what the agency’s leader called a “deeply troubling” trend. U. of I. computer science professor Sheldon Jacobson, who has studied aviation security system analysis for 25 years and is among the researchers whose work led to the development of the TSA PreCheck screening system, says TSA’s concerns over the 2019 increase come without context. “What if they found 10 firearms, or what if they found 10,000?