Faculty and Students

A list of active members and alumni of the Theory of Computing group



Eric Bach

  • CS-4391


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

Jin-Yi Cai

  • CS-4393


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

Ilias Diakonikolas

  • CS-4387


Algorithms, Learning Theory, Machine Learning, Applied Probability

Dieter van Melkebeek

  • CS-4390


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

Christos Tzamos

  • CS-4375


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

Rishab Goyal

  • CS-4373


Cryptography and Computer Security

Affiliated Faculty

Alberto Del Pia

Algorithms for combinatorial, stochastic, and online optimization

Paris Koutris

Data processing, data pricing, and managing data under uncertainty

Steffen Lempp

Computability theory and applications to model theory

Sebastien Roch

Applied probability, statistics

Postdoctoral Researchers

Sushrut Karmalkar


Jasper Lee


Graduate Students

Evangelia Gergatsouli


Vasilis Kontonis


Jeremy McMahan


Ryan Moreno


Jongho Park


Thanasis Pittas


Nicollas Sdroievski


Yuxin Sun


Nikos Zarifis




Andrew Morgan

PhD 2022

Thesis: Lower Bounds Related to Polynomial Identity Testing, Circuit Minimization, and Inversion Minimization

Advisor: Dieter van Melkebeek


Yifeng Teng

PhD 2021 › Google

Thesis: The Power of Simple Pricings for Revenue and Welfare Maximization

Advisor: Shuchi Chawla


Tianyu Liu

PhD 2020

Thesis: Approximate Complexity in Statistical Mechanics: Counting and Sampling in the Six- and Eight-Vertex Models

Advisor: Jin-Yi Cai

Artem Govorov

PhD 2020

Thesis: Complexity and Expressibility of Counting Graph Homomorphism Problems

Advisor: Jin-Yi Cai

Shuai Shao

PhD 2020

Thesis: Complexity Classification of Counting Problems on Boolean Variables

Advisor: Jin-Yi Cai

Ali Vakilian

Postdoc 2020 › postdoc Toyota Technological Institute

Advisor: Ilias Diakonikolas


Benjamin Miller

PhD 2019 › Google

Thesis: Simple and Robust Mechanism Design

Advisor: Shuchi Chawla

Gautam Prakriya

PhD 2019 › Postdoc at the Chinese University of Hong Kong

Thesis: Derandomizing Isolation and Polynomial Identity Testing

Advisor: Dieter van Melkebeek


Dimitris Paparas

Postdoc 2017 › Google

Advisor: Shuchi Chawla

Baris Aydinlioglu

PhD 2017

Thesis: A Study of the NEXP vs. P/poly Problem and its Variants

Advisor: Eric Bach


Heng Guo

PhD 2015 › postdoc at Queen Mary University of London › faculty at University of Edinburgh

Thesis: Complexity Classification of Exact and Approximate Counting Problems

Advisor: Jin-Yi Cai

Seeun William Umboh

PhD 2015 › postdoc at TU Eindhoven, Netherlands › University of Sydney

Thesis: Towards a Unified Analysis Framework for Online Network Design

Advisor: Shuchi Chawla

Tyson Williams

PhD 2015 › Blocher Consulting

Thesis: Advances in the Computational Complexity of Holant Problems

Advisor: Jin-Yi Cai


Andrew Bridy

PhD (Math) 2014 › University of Rochester › Texas A&M University › Yale University

Thesis: The Artin-Mazur Zeta Function of a Rational Map in Positive Characteristic

Advisor: Eric Bach

David Malec

PhD 2014 › postdoc at the University of Maryland, and consultant with Cramton Associates

Thesis: Approximations in Bayesian mechanism design for multi-parameter settings

Advisor: Shuchi Chawla


Balu Sivan

PhD 2013 › postdoc at Microsoft Research, Redmond › research scientist at Google Research NY

Thesis: Prior Robust Optimization

Advisor: Shuchi Chawla

Holger Dell

Postdoc 2013 › Assistant Professor at Saarland University › Associate Professor at IT University of Copenhagen

Advisor: Dieter van Melkebeek


Siddharth Barman

PhD 2012 › postdoc at CMI, Caltech › faculty at IISc, Bangalore

Thesis: Approximation Algorithms for Network Design and Partitioning Problems

Advisor: Shuchi Chawla

Matthew Anderson

PhD 2012 › postdoc at Cambridge University › faculty at Union College

Thesis: Advancing Algebraic and Logical Approaches to Circuit Lower Bounds

Advisor: Dieter van Melkebeek


Michael Kowalczyk

PhD 2010 › faculty at Northern Michigan University

Thesis: Dichotomy Theorems for Holant Problems

Advisor: Jin-Yi Cai

Jeff Kinne

PhD 2010 › faculty at Indiana State University

Thesis: Deterministic Simulations and Hierarchy Theorems for Randomized Algorithms

Advisor: Dieter van Melkebeek


Sylvain Perifel

Postdoc 2008 › Assistant/Associate Professor at the University of Paris

Advisor: Dieter van Melkebeek

Scott Diehl

PhD 2008 › faculty at Siena College › Google Madison

Thesis: Time-Space Lower Bounds for Satisfiability and Related Problems on Randomized Machines

Advisor: Dieter van Melkebeek


Andrew Shallue

PhD (Math) 2007 › postdoc at University of Calgary › Associate Professor of Mathematics Illinois Wesleyan University

Thesis: Two Number-Theoretic Algorithms that Illustrate the Power and Limitations of Randomness

Advisor: Eric Bach


Denis Charles

PhD 2005 › researcher at Microsoft Research, Redmond

Thesis: Computational Aspects of Modular Forms and Elliptic Curves

Advisor: Eric Bach


Venkat Chakaravarthy

PhD 2004 › IBM Research, New Delhi

Thesis: On Some Computational Problems in Randomization, Interaction and Inapproximability

Advisor: Jin-Yi Cai