PEOPLE

Faculty and Students

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


People

Faculty

Eric Bach

  • CS-4391

  • bach@cs.wisc.edu

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

Jin-Yi Cai

  • CS-4393

  • jyc@cs.wisc.edu

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

  • ilias@cs.wisc.edu

Algorithms, Learning Theory, Machine Learning, Applied Probability

Dieter van Melkebeek

  • CS-4390

  • dieter@cs.wisc.edu

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

Christos Tzamos

  • CS-4375

  • tzamos@cs.wisc.edu

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

Rishab Goyal

  • CS-4373

  • rishab.goyal@wisc.edu

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

  • skarmalkar@wisc.edu

Jasper Lee

  • jasper.lee@wisc.edu

Graduate Students

Evangelia Gergatsouli

  • gergatsouli@wisc.edu

Vasilis Kontonis

  • kontonis@wisc.edu

Jeremy McMahan

  • jmcmahan@wisc.edu

Ryan Moreno

  • rmoreno@wisc.edu

Jongho Park

  • jongho.park@wisc.edu

Thanasis Pittas

  • pittas@wisc.edu

Nicollas Sdroievski

  • sdroievski@wisc.edu

Yuxin Sun

  • yxsun@cs.wisc.edu

Nikos Zarifis

  • zarifis@wisc.edu

Alumni

2022

Andrew Morgan

PhD 2022

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

Advisor: Dieter van Melkebeek

2021

Yifeng Teng

PhD 2021 › Google

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

Advisor: Shuchi Chawla

2020

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

2019

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

2017

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

2015

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

2014

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

2013

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

2012

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

2010

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

2008

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

2007

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

2005

Denis Charles

PhD 2005 › researcher at Microsoft Research, Redmond

Thesis: Computational Aspects of Modular Forms and Elliptic Curves

Advisor: Eric Bach

2004

Venkat Chakaravarthy

PhD 2004 › IBM Research, New Delhi

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

Advisor: Jin-Yi Cai