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

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

Theory, Quantum

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

Quantum Computing, Complexity, Optimization, Stochastic Processes

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 

Related News