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
Dakshita Khurana cryptography, privacy, security
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

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

PhD student Edward Hutter

Hutter's Work On Communication Costs Leads to DOE Computational Science Graduate Fellowship

December 4, 2018   PhD student Edward Hutter's work in communication-cost analysis and reduction earns him a Department of Energy Computational Science Graduate Fellowship.
Assistant Professor Edgar Solomonik

Solomonik Recognized for Early Career Work Aimed at Improving HPC Performance

November 14, 2018   The IEEE Computer Society has recognized Assistant Prof. Edgar Solomonik’s research with the TCHPC Award for Excellence for Early Career Researchers in HPC.
CS Professor Sheldon Jacobson

Jacobson Recognized for Research That Transformed Passenger Screening After 2001 Attacks

November 12, 2018   Professor Sheldon Jacobson and three former students laid the groundwork for TSA PreCheck passenger screening. That work has been recognized with an IMPACT Prize.
CS Professor Sheldon Jacobson

INFORMS Podcast Features Illinois CS Professor Sheldon Jacobson

November 2, 2018  

Resoundingly Human podcast -- Illinois CS Professor Sheldon Jacobson appears on the Institute for Operations Research and the Management Sciences' podcast to discus his IMPACT Prize from the group. The prize recognized work by Jacobson and his students that helped transform air-travel security.

William Gropp, the Thomas M. Siebel Chair in Computer Science and Director of the National Center for Supercomputing Applications

BIG BLACK BOX: We Are On The Verge Of Building An Exascale Computer. But What Does That Mean?

October 13, 2018  

New Scientist -- The roadmap for exascale hardware is fairly well laid out. Software and algorithms to run across potentially billions of cores may be trickier. “Every generation of supercomputers leaves some users behind,” says William Gropp, CS professor and director of the National Center for Supercomputing Applications. “That’s been a constant problem and I think we’re going to see it again.” (behind paywall)