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.

Shuchi Chawla

  • CS-4373


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

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.

Affiliated Faculty

Alberto Del Pia

Algorithms for combinatorial, stochastic, and online optimization

Justin Hsu

Formal Verification, Randomized Algorithms, Differential Privacy

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

Ali Vakilian


Graduate Students

Jialu Bao


Evangelia Gergatsouli


Artem Govorov


Vasilis Kontonis


Tianyu Liu


Jeremy McMahan


Ryan Moreno


Andrew Morgan


Jongho Park


Rojin Rezvan


Nicollas Sdroievski


Shuai Shao


Yuxin Sun


Yifeng Teng


Nikos Zarifis




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