Theory and Algorithms
Theoretical 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|
|Alexandra Kolla||complexity theory, spectral methods for graph algorithms|
|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|
|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|
|Manoj Prabhakaran, IIT Bombay||cryptography, secure multi-party computation|
Related Theory and Algorithms Research Efforts and Groups
- Information Trust Institute (ITI) in the Coordinated Science Lab
- Carl R. Woese Institute for Genomic Biology (IGB)
- Theory and Algorithms Group
To receive weekly reminders and announcements of Theory & Algorithms seminars, please sign up for the theory-seminar mailing list.
Theory and Algorithms Research News
WCIA-TV -- A submarine created by Illinois Computer Science students and other students from the College of Engineering is headed to a national competition. The autonomous submarine will compete in the International Robosub Competition in San Diego.
The University Network -- A team of researchers led by Assistant Professor Mohammed El-Kebir has developed a new method to track the spread of cancer cells, yielding a clearer understanding of cancer migration than ever before. Their algorithm, called MACHINA, tracks the spread of cancer cells.
WXIA-TV Atlanta -- CS Professor Sheldon Jacobson is interviewed in this story on the arrest of a man who rushed a Delta Airlines plane on the tarmac at Atlanta's airport. "It doesn't scare me because there were enough checkpoints and layers in place ..." Jacobson appears at 1:42 in the video version of the story.
The Engineer -- CS Assistant Professor Jian Peng and other Illinois researchers have developed a new algorithm to eliminate the compromise between high resolution and high frequency in satellite imagery by fusing data into one integrated product. Coverage also by LaserFocusWorld and AgPro.
WBEZ's Morning Shift -- Going into the NCAA Tournament, WBEZ sports contributor Cheryl Raye-Stout created her own bracket to compete with one created by CS Professor Sheldon Jacobson's Bracket Odds website. With the tournament now over, who had the better bracket?