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

Assistant Professor Jian Peng

PNAS Studies Look at Lung Cancer LncRNA, Hi-C Clustering, and More

June 25, 2019  

Genome Web -- Genome Web highlights new research from Assistant Professor Jian Peng and colleagues at the University of California-San Diego that yielded scHiCluster, a single-cell clustering algorithm.

Professor Sheldon Jacobson

This Isn’t How It Was Supposed to Work: Has PreCheck Become Unchecked?

June 20, 2019  

RealClear Defense -- Professor Sheldon Jacobson writes an opinion piece on airport security and TSA PreCheck. "Long airport lines, intensive airport screening, and the summer travel season tend to go together. Already, this year seems to be keeping with that tradition, but what if it didn't have to be that way?"

Founder Professor on Engineering Tandy Warnow

Linguistics Paper Co-authored By Warnow Settled Key Questions, Honored for Its Influence

June 11, 2019   Tandy Warnow and collaborator Donald Ringe developed mathematical models that assumed language evolution followed a treelike pattern.
Assistant Professor Bo Li

Scientists Help Artificial Intelligence Outsmart Hackers

May 14, 2019  

Science -- Researchers say they have found a new way to give AI a defensive edge against adversarial attacks based on patterns hidden in images. Bo Li, a computer scientist at the University of Illinois who was not involved in the work, says distinguishing apparent features from hidden features is a “useful and good research direction” but also still needs more work.

Assistant Professor Bo Li

AI Can Now Defend Itself Against Malicious Messages Hidden In Speech

May 10, 2019  

Nature -- Bo Li, a computer scientist at the University of Illinois at Urbana-Champaign, and her co-authors wrote an algorithm that transcribes a full audio clip and, separately, just one portion of it. If the transcription of that single piece doesn’t closely match the corresponding part of the full transcription, the program throws a red flag — the sample might have been compromised.