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 (joining Fall '18)

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


Upcoming Talks

No upcoming talks.

Past Talks »

Fall 2017 Courses

  • CS 520:
    Theory of Computing
    Eric Bach
  • CS 577:
    Intro to Algorithms
    Jin-Yi Cai
  • CS 710:
    Computational Complexity
    Dieter van Melkebeek
  • CS 880:
    Algorithms for Massive Datasets
    Shuchi Chawla
Previously Offered Courses »