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 joining fall 2019; 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

Google Faculty Research Awards

CS Faculty Receive Google Faculty Research Awards

April 11, 2019   Google Faculty Research Awards are given to a select group conducting computer science and engineering research. This year two Illinois CS faculty were chosen, as well as three ECE faculty who are CS affiliates.
CS Professor Sheldon Jacobson

Should We Embrace Metro’s Broken Escalators for Keeping Us In Shape?

April 9, 2019  

The Washington Post -- Escalators in Washington, D.C., Metro stations often break. But that may be a good thing, according to research from Illinois CS Professor Sheldon Jacobson. “When people use public transit, they typically must walk (or) cycle to the stop/station, and on the back end, do the same," Jacobson said via email. “Also, during the transit ride, they may stand (more calories burned)."

CS Professor Sheldon Jacobson

Illinois Professor Improves Airport Security Systems

April 8, 2019  

The Daily Illini -- After the events of Sept. 11, 2001, the federal government increased airport security and changed the system for screening passengers. In 2011, airports introduced Transportation Security Administration precheck, a process developed with the help of work done by Sheldon Jacobson, a Computer Science professor.

CS Professor Sheldon Jacobson

The Fight in Illinois Begins Again to Protect Your Vote

April 5, 2019  

Chicago Sun-Times -- "Gerrymandering has been around since the early days of the Republic, but powerful computers and big data have made the practice much more effective. … Scientists at the University of Illinois proposed a way to take politics out of redistricting by letting a carefully designed algorithm draw the maps," referencing research by Professor Sheldon Jacobson.

CS Professor Sheldon Jacobson

Airport Officials, TSA to Talk Prevention Following Security Breach, Attack

April 3, 2019  

KUTV -- Illinois CS Professor Sheldon Jacobson says a security breach at the airport in Salt Lake City a “fairly isolated incident with a bad outcome,” and said one to two airport security breaches happen each month nationwide.