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, 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
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

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

To receive weekly reminders and announcements of Theory & Algorithms seminars, please sign up for the theory-seminar mailing list.

Theory and Algorithms Research News

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.
Professor Karrie Karahalios

Karahalios Named University Scholar, Hopes Honor Will Propel Work on Autism, Algorithm Awareness

July 30, 2019   Karahalios, an expert on HCI and social computing, is the first Illinois CS faculty member named a University Scholar since Professor Saurabh Sinha in 2017.
Professor Sheldon Jacobson

An Algorithmic Approach to Drawing Electoral District Boundaries

July 9, 2019  

WTKF-FM -- The Coastal Daybreak show on WTKF in Morehead City, N.C., talks with Professor Sheldon Jacobson about his reserach on redistricting, a hot-button issue in North Carolina and the subject of an ongoing court case in the state.

Assistant Professor Jian Peng

PNAS Studies Look at Lung Cancer LncRNA, Hi-C Clustering, and More

June 25, 2019  

Genome Web -- Genome Web highlights new research from Assistant Professor Jian Peng and colleagues at the University of California-San Diego that yielded scHiCluster, a single-cell clustering algorithm.