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 and Their Research Interests

Timothy Chan computational geometry
Chandra Chekuri algorithms, optimization 
Jeff Erickson computational geometry and topology, algorithms 
Michael Forbes computational complexity
Brighten Godfrey networked systems theory, distributed algorithms
Sariel Har-Peled computational geometry, geometric approximation algorithms
Sheldon Jacobson optimization, operations research
Alexandra Kolla complexity theory, spectral methods for graph algorithms 
Ruta Mehta algorithmic game theory, mathematical economics, efficient algorithms
Leonard Pitt  AI and theoretical computing 
Matus Telgarsky machine learning theory
Mahesh Viswanathan algorithmic verification of cyberphysical systems 
Tandy Warnow multiple sequence alignment, phylogenomics, metagenomics, and historical linguistics

Affiliate Faculty

Karthik Chandrasekaran, Industrial & Enterprise Systems Engineering combinatorial optimization, integer programming, probabilistic methods and analysis, randomized algorithms  
Negar Kiyavash, Electrical & Computer Engineering and Industrial & Enterprise Systems Engineering learning, statistical signal processing, and information theory; causality; network forensics 
Rakesh Nagi, Industrial & Enterprise Systems Engineering social networks, graph algorithms, applied operations research, discrete optimization

Adjunct Faculty

Manoj Prabhakaran, IIT Bombay cryptography, secure multi-party computation 

Related Theory and Algorithms Research Efforts and Groups


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

Theory and Algorithms Research News

CS Assistant Professor Jian Peng

Algorithm Overcomes Compromise In Acquisition Of Satellite Imagery

June 5, 2018  

The Engineer -- CS Assistant Professor Jian Peng and other Illinois researchers have developed a new algorithm to eliminate the compromise between high resolution and high frequency in satellite imagery by fusing data into one integrated product. Coverage also by LaserFocusWorld and AgPro.

CS Professor Sheldon Jacobson

Whose NCAA Bracket Did Better? WBEZ Expert vs. The Machine

April 3, 2018  

WBEZ's Morning Shift -- Going into the NCAA Tournament, WBEZ sports contributor Cheryl Raye-Stout created her own bracket to compete with one created by CS Professor Sheldon Jacobson's Bracket Odds website. With the tournament now over, who had the better bracket?

PhD candidate Faraz Faghri

International Team That Includes University of Illinois Computer Scientists Confirms New Link To ALS

March 29, 2018   An international team that includes Illinois Computer Science PhD candidate Faraz Faghri and Professor Roy H. Campbell has proven a new a genetic link to ALS.
Assistant Professor Ruta Mehta

Mehta Earns NSF CAREER Award, Will Target Research on Equilibrium Computation

March 14, 2018   Assistant Professor Ruta Mehta will explore problems that sit at the intersection of theory and practical applications in economics, cryptography, and other areas.
CS Professor Sheldon Jacobson

Science Of Upsets: Prof Has Formula That Doubles Your Shot

March 14, 2018  

The Associated Press -- AP interviews CS Professor Sheldon Jacobson about his model for upset prediction, a story that was picked up by The New York Times, the Washington Post, ESPN , ABC News, Fox SportsYahoo! Sports, the National Post, and dozens of others.