Theory of Computing


Eric Bach

Computational number theory and algebra, analysis of randomized and quantum algorithms, cryptography.

Jin-Yi Cai

Complexity theory of counting problems: Classification Program for partition functions of Graph Homomorphisms, Spin Systems, Counting Constraint Satisfaction Problems, and Holant Problems.

Shuchi Chawla

Algorithms for combinatorial, stochastic, and online optimization; applications to economics; algorithmic mechanism design; learning theory.

Dieter van Melkebeek

Complexity theory: lower bounds for NP-complete problems, pseudorandomness and derandomization, quantum computing.

Christos Tzamos

Algorithmic game theory and mechanism design, learning theory, fine-grained complexity.

Related Faculty

Nigel Boston

Number theory, group theory, computational algebra, coding theory, cryptography, optimization

Susan Coppersmith

Quantum computing

Alberto Del Pia

Mixed-integer optimization, polyhedral combinatorics, combinatorial optimization

Paris Koutris

Data processing for massively parallel systems, data pricing, and managing data under uncertainty

Steffen Lempp

Computability theory and applications to model theory

Sebastien Roch

Applied probability, statistics

Related Postdoctoral Researchers

Irene Giacomelli



Upcoming Talks

Past Talks »

Fall 2018 Courses

  • CS 520:
    Theory of Computing
    Jin-Yi Cai
  • CS 577:
    Intro to Algorithms
    Shuchi Chawla and Christos Tzamos
  • CS 809:
    Mathematical Techniques in the Analysis of Algorithms
    Eric Bach
Previously Offered Courses »