Theory and Algorithms

Theory and Algorithms - an illustrationTheoretical 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, Affiliate 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
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
Yuan Zhou, Industrial & Enterprise Systems Engineering Maching Learning Theory, Operations Research, Combinatorial Optimization

Adjunct Faculty

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

Seminars

Theory and Algorithms Research News

Sheldon Jacobson

TSA caught people trying to fly with more guns than ever in 2019. Experts have questions.

January 21, 2020  

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?

The Institute for Computational Redistricting hopes to help bring transparency to the decennial redistricting process.

Computational Redistricting: Drawing the Maps

January 10, 2020   The Institute for Computational Redistricting hopes to help bring transparency to the decennial redistricting process.
Profs. Tarek Abdelzaher and Timothy M. Chan have been named ACM Fellows, Profs. Karrie Karahalios and Hari Sundaram have been named ACM Distinguished Members.

Abdelzaher, Chan, Karahalios, and Sundaram Honored by ACM

December 18, 2019   Profs. Tarek Abdelzaher and Timothy M. Chan have been named ACM Fellows, Profs. Karrie Karahalios and Hari Sundaram have been named ACM Distinguished Members.
Profs. Sheldon Jacobson, Klara Nahrstedt, and Tao Xie are among 443 people to be awarded the distinction of AAAS Fellow this year.

Jacobson, Nahrstedt, and Xie Among Eight 2019 AAAS Fellows From Illinois

December 2, 2019   Profs. Sheldon Jacobson, Klara Nahrstedt, and Tao Xie are among 443 people to be awarded the distinction of AAAS Fellow this year.
Five accomplished Illinois Computer Science master’s students have been recognized for their academic achievements and leadership.

Meet the Siebel Scholars Class of 2020

October 2, 2019   Five accomplished Illinois Computer Science master’s students have been recognized for their academic achievements and leadership.