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

Professor Lenny Pitt

Pitt Prepares To Depart Illinois CS, the Department He Helped Shape Over Three Decades

March 14, 2019   Pitt joined Illinois CS in 1985 and had a prominent hand in CS + X, the growth of teaching faculty, and the culture of one of the leading CS departments.
Professor Jiawei Han

Professor Jiawei Han Named Aiken Endowed Chair

February 7, 2019   Han is the second-ever Aiken Chair, a position he plans to use to maintain Illinois' leadership in data-mining research.
Trala CTO Vishnu Indukuri

CS Graduate Indukuri Using $1.29M In Venture Backing From LinkedIn CEO And Others To Fine Tune Trala

February 5, 2019   Illinois CS graduate sees venture funding as key to expanding content of violin app, and boosting its sales.
CS Professor Sheldon Jacobson

Want To Lose Weight? Give Public Transit A Try

January 30, 2019  

Mobility Lab -- A new study by the University of Illinois and Georgia Tech attaches solid numbers to what seems like common sense. “The results indicate that when more people opt to use public transit ... obesity rate tends to drop,” said Sheldon H. Jacobson, a co-author and professor at Illinois. Also covered by the New York Post.

Professor and Education Innovation Fellow Jeff Erickson

Software: It Is All In The Details

January 6, 2019  

HACKADAY -- "We were excited to see Jeff Erickson is publishing his algorithms book distilled from teaching at the University of Illinois. ... There are worse places to learn about algorithms than UIUC; they have a long history in both real and fictional computing."