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.

Postdoctoral Researchers

Dimitris Paparas

Algorithms, Complexity Theory, Computational Economics / Algorithm Game Theory, and Optimization


  • Barış Aydınlıoğlu, PhD 2017
  • Heng Guo, PhD 2015 › postdoc at Queen Mary University of London
  • Seeun William Umboh, PhD 2015 › postdoc at TU Eindhoven, Netherlands
  • Tyson Williams, PhD 2015 › Blocher Consulting
  • David Malec, PhD 2014 › postdoc at the University of Maryland
  • Balasubramanian (Balu) Sivan, PhD 2013 › postdoc at Microsoft Research, Redmond
  • Siddharth Barman, PhD 2012 › postdoc at the Center for the Mathematics of Information, Caltech
  • Matthew Anderson, PhD 2012 › postdoc at Cambridge University
  • Michael Kowalczyk, PhD 2010 › assistant professor at Northern Michigan University
  • Jeffrey (Jeff) Kinne, PhD 2010 › assistant professor at Indiana State University
  • Scott Diehl, PhD 2008 › assistant professor at Siena College
  • Denis Charles, PhD 2005 › postdoc at Microsoft Research, Redmond
  • Venkat Chakravarthy, PhD 2004 › IBM Research, New Delhi

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 »