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), Emily 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
Computation Geometry, Computational Biology, Parallel Algorithms
Graph Grammars
Computational geometry, algorithms, data structures, fine-grained complexity
Combinatorial Optimization, Integer Programming, Probabilistic Methods and Analysis, Randomized Algorithms
Algorithms, Combinatorial Optimization
Societal impact of AI, algorithmic game theory, human-AI collaboration
Applied algorithms, combinatorial optimization, mixed integer linear programming
Computational geometry, computational topology, graph algorithms
Complexity theory; algebraic complexity theory; pseudorandomness; randomness, algebra, and computation
Computational geometry and topology, graph algorithms
Algorithms, Game Theory, Fair Division
Algorithms for and Analysis of Networks and Distributed Systems
Coding Theory, Pseudorandomness, Complexity Theory, Quantum Computing, Algorithms, Optimization
Approximation Algorithms, Computational Geometry
Probability, Operations Research, Applications
Reinforcement learning theory, machine learning theory
Cryptography, complexity, algorithms
Algorithms, Complexity, Algorithmic Game Theory, Online Algorithms, EconCS, Dynamical systems, Competitive equilibrium, Nash equilibrium, Data economies, Fair division
Social Networks, Graph Algorithms, Applied Operations Research, Discrete Optimization, GPU-Accelerated Algorithms
Logic and decidability, mathematical models of computation, verification and synthesis of algorithms
Economics of Data, Economic Paradigms for Collaborative Learning, Computational Social Choice, Algorithm Design
Embodied AI in agriculture, construction, and marine applications.
Quantum computing, Computational Complexity, Stochastic Processes
Computational Genomics, Sketching and Sub-linear Data Structures
Numerical algorithms, parallel algorithms, quantum computation
Coding Theory, Pseudorandomness, Complexity Theory, Quantum Computing, Algorithms, Optimization
Algorithm design; Logic; Automata theory
Discrete algorithms and statistical learning
Learning Theory
Cryptography, Security
Computational learning theory
Adjunct Faculty
Complexity Theory, Spectral Methods for Graph Algorithms
Cryptography, Secure Multi-Party Computation