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

Chandra Chekuri algorithms, optimization 
Jeff Erickson computational geometry and topology, algorithms 
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 
Manoj Prabhakaran cryptography, secure multi-party computation 
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 

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

Sheldon Jacobson

Study Offers Efficient Alternative for Ebola Screening Program

March 27, 2016   In a recent paper, Sheldon H. Jacobson and his colleagues suggest an alternative policy for Ebola entry screening.
CS and Bioengineering Professor Tandy Warnow

Warnow Named a Fellow of ACM

December 6, 2015   CS and Bioengineering Professor Tandy Warnow has been named a 2015 Fellow of the Association for Computing Machinery.
News story image

Kolla Receives NSF CAREER Award to Investigate NP-Hard Problems

November 1, 2015   CS Assistant Professor Alexandra Kolla recently received a young faculty NSF CAREER award.

CS Welcomes Seven New Faculty Members

September 28, 2015   Seven new faculty members will be joining CS @ ILLINOIS over the coming year.
Sheldon Jacobson

Is Backscatter X-ray a Safe Tool for Airport Security?

September 28, 2015   CS Professor Sheldon H. Jacobson helped assemble a new NAS report on backscatter X-ray machines.