Theory and Algorithms

Theoretical computer science studies the foundations computing from a rigorous and mathematical point of view. Core topics include models of computing, design and analysis of algorithms, data structures, protocols and mechanisms, and lower bounds.

Our faculty study algorithms in many diverse areas (computational geometry & topology, graphs, optimization, approximation, randomization), data structures, cryptography and secure computation, economics and computation, complexity theory, foundations of machine learning, and applications to several areas including operations research, computational biology, parallel & distributed computing, and networking to name a few. Our research, in addition to its fundamental importance, has many near and long term applications in Computer Science and beyond.

Strengths and Impact

Publications

The group has an outstanding and prolific publication record in the top conferences and journals of TCS. The faculty have received several best paper awards and mentions. Some recent highlights of faculty awards: (1) ACM Fellow (Amato, Chan, Warnow), (2) AAAS Fellow (Jacobson), (3) George E Kimball Medal from INFORMS (Jacobson), (5) David F Baker Distinguished Research Award from Institute of Industrial and Systems Engineering (IISE) (Jacobson), (6) NSF CAREER Award (Garg, Mehta, Solomonik, Telgarsky), and (7) Chairs or Professorships (Chan, Chekuri, Erickson, Jacobson, Warnow).

PhD Placements

The group has graduated several doctoral students who have gone onto excellent careers in academia and industrial research. The more recent academic cohort includes: Hsien-chih Chang (Dartmouth), Alina Ene (Boston U, NSF CAREER, Sloan Fellowship), Kyle Fox (UT Dallas, NSF CAREER), Sung jin Im (UC Merced, NSF CAREER), Nirman Kumar (U of Memphis), Hemanta Maji (Purdue), Ben Moseley (CMU, NSF CAREER), Amir Nayyeri (Oregon State U, NSF CAREER), Kent Quanrud (Purdue), Ben Raichel (UT Dallas, NSF CAREER), Jason Sauppe (U Wisconsin at La Crosse).

Research Efforts and Groups

Seminars

To receive weekly reminders and announcements of Theory & Algorithms seminars, please sign up for the theorycs mailing list.
Illinois Computer Science Speaker Series: brings prominent leaders and experts to campus to share their ideas and promote conversations about important challenges and topics in the discipline.

Faculty & Affiliate Faculty

Nancy M. Amato

Geometry, Parallel Algorithms, Computational Biology

Timothy Chan

Computational Geometry, Algorithms, Data Structures

Karthik Chandrasekaran, Industrial & Enterprise Systems Engineering

Combinatorial Optimization, Integer Programming, Probabilistic Methods and Analysis, Randomized Algorithms

Chandra Chekuri

Algorithms, Combinatorial Optimization, Mathematical Programming, Graphs

Kate Donahue

Societal impact of AI, algorithmic game theory, human-AI collaboration

Mohammed El-Kebir

Combinatorial Optimization, Integer Linear Programming, Computational Biology

Jeff Erickson

Computational Geometry and Topology, Algorithms

Michael A. Forbes

Pseudorandomness, Algebraic Computation, Computational Complexity

Jugal Garg, Industrial & Enterprise Systems Engineering

Algorithms, Game Theory, Fair Division

Brighten Godfrey

Algorithms for and Analysis of Networks and Distributed Systems

Fernando Granha Jeronimo

Theory, Quantum

Sariel Har-Peled

Computational Geometry, Geometric Approximation Algorithms

Sheldon Jacobson

Optimization, Operations Research

Nan Jiang

Reinforcement Learning Theory, Machine Learning, Sample Complexity Analysis

Dakshita Khurana

Cryptography, Secure Computation, Zero-Knowledge, Differential Privacy

Ruta Mehta

Algorithmic Game Theory, Mathematical Economics, Efficient Algorithms

Rakesh Nagi, Industrial & Enterprise Systems Engineering

Social Networks, Graph Algorithms, Applied Operations Research, Discrete Optimization, GPU-Accelerated Algorithms

Ling Ren

Cryptography, Distributed Algorithms

Makrand Sinha

Quantum Computing, Complexity, Optimization, Stochastic Processes

Edgar Solomonik

Parallel Algorithms, Numerical Methods, Communication Cost Analysis, Quantum Computation

Mahesh Viswanathan

Automata theory, logic, algorithmic verification, security

Tandy Warnow

Graph Algorithms, Statistical Estimation, Heuristics for NP-Hard Optimization Problems, Experimental Algorithmics, Applications to Grand Challenges in Biology and Historical Linguistics

Yupeng Zhang, Electrical & Computer Engineering

Cryptography, Security

Han Zhao

Machine Learning, Information Theory, Representation Learning