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
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

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

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 William Gropp, the Thomas M. Siebel Chair in Computer Science

Siebel Chair Gift Keeps Giving To Gropp And Illinois CS Researchers

October 12, 2018   As the Thomas M. Siebel Chair in Computer Science, Professor Bill Gropp says he has a tool that lets him jump-start interesting science.
CS Professor Karrie Karahalios

Facebook, Twitter Will Face GOP Questions of Political Bias at Congressional Hearings

September 4, 2018  

Variety -- Tech companies keep algorithms secret for competitive reasons, but that has led to alternative -- often incorrect -- explanations of how they work. A study by U. of Illinois researchers, including CS Professor Karrie Karahalios, found that Facebook users often develop their own “folk theories” about how it curates its newsfeed.

 

CS student Ajay Shekar

Artificial Intelligence And Healthcare: The Role Of The Computer Scientist

August 21, 2018  

Smile Politely -- Ajay Shekar is a master's student in Computer Science working on applying machine-learning and deep-learning techniques on medical image datasets. He wants to create a tool that can help predict Parkinson’s Disease.

 

Illinois AUV team leader and student Shubhankar Agarwal

UI Submarine Goes To National Competition

July 23, 2018  

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.

Assistant Professor Mohammed El-Kebir

Method Revolutionizes Tracking The Spread Of Cancer

July 17, 2018  

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.