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.

Shuchi Chawla

  • CS-4373

  • shuchi@cs.wisc.edu

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

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.

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

  • vakilian@mit.edu

Graduate Students

Jialu Bao

  • jialu@cs.wisc.edu

Evangelia Gergatsouli

  • gergatsouli@wisc.edu

Artem Govorov

  • hovarau@wisc.edu

Vasilis Kontonis

  • kontonis@wisc.edu

Tianyu Liu

  • tl@cs.wisc.edu

Jeremy McMahan

  • jmcmahan@wisc.edu

Andrew Morgan

  • amorgan@wisc.edu

Jongho Park

  • jongho.park@wisc.edu

Rojin Rezvan

  • rezvansangsa@wisc.edu

Nicollas Sdroievski

  • sdroievski@wisc.edu

Shuai Shao

  • sh@cs.wisc.edu

Yuxin Sun

  • yxsun@cs.wisc.edu

Yifeng Teng

  • yifengt@cs.wisc.edu

Nikos Zarifis

  • zarifis@wisc.edu

Student Awards

Alumni

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