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
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).
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).
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
Geometry, Parallel Algorithms, Computational Biology
Computational Geometry, Algorithms, Data Structures
Combinatorial Optimization, Integer Programming, Probabilistic Methods and Analysis, Randomized Algorithms
Algorithms, Combinatorial Optimization, Mathematical Programming, Graphs
Graphs, Information Theory, Algorithms, Machine Learning
Combinatorial Optimization, Integer Linear Programming, Computational Biology
Computational Geometry and Topology, Algorithms
Pseudorandomness, Algebraic Computation, Computational Complexity
Algorithms, Game Theory, Fair Division
Algorithms for and Analysis of Networks and Distributed Systems
Computational Geometry, Geometric Approximation Algorithms
Optimization, Operations Research
Reinforcement Learning Theory, Machine Learning, Sample Complexity Analysis
Cryptography, Secure Computation, Zero-Knowledge, Differential Privacy
Algorithmic Game Theory, Mathematical Economics, Efficient Algorithms
Social Networks, Graph Algorithms, Applied Operations Research, Discrete Optimization, GPU-Accelerated Algorithms
Cryptography, Distributed Algorithms
Parallel Algorithms, Numerical Methods, Communication Cost Analysis, Quantum Computation
Deep Learning Theory
Automata theory, logic, algorithmic verification, security
Graph Algorithms, Statistical Estimation, Heuristics for NP-Hard Optimization Problems, Experimental Algorithmics, Applications to Grand Challenges in Biology and Historical Linguistics
Machine Learning, Information Theory, Representation Learning
Adjunct Faculty
Complexity Theory, Spectral Methods for Graph Algorithms
Cryptography, Secure Multi-Party Computation
Second Year of Pandemic Deadlier for Middle Aged Than the First, Analysis Finds
News | November 17, 2022
Five Travel Myths Debunked for Thanksgiving Weekend
News | November 15, 2022
The Perils of Polling and Election Forecasting
News | November 1, 2022
The Health of Our Nation's Health Care System is Under Attack
News | October 31, 2022