Theory PhDs awarded in the Department

Péter Hajnal, Ph.D. 1988, currently at the University of Szeged, Hungary
Thesis: "The Complexity of Graph Problems"
Advisors: Janos Simon, László Babai, Endre Szemerédi

Mario Szegedy, Ph.D. 1989, currently at Rutgers University
Thesis: "Algebraic Methods in Lower Bounds for Computational Models with Limited Communication"
Advisors: László Babai, Janos Simon

Carsten Lund, Ph.D. 1991, currently at AT&T Labs Research
Thesis: "Computational Complexity of Interactive Proof Systems"
Advisors: Lance Fortnow, László Babai

Stephen A. Fenner, Ph.D. 1991, currently at The University of South Carolina
Thesis: "Chains, Gaps, and Genericity: Three Topics in Structural Complexity"
Advisor: Stuart Kurtz

Jose Soares, Ph.D. 1992, currently at Sao Paulo University, Brasil
Thesis: "Graph Spanners"
Advisor: László Babai

Sundar Vishwanathan, Ph.D. 1992, currently at IIT Bombay, India
Thesis: "Online Algorithms for Graph Problems"
Advisor: Howard Karloff

Robert Beals, Ph.D. 1993, currently at the Institute for Defense Analyses
Thesis: "Algorithms for Finite Groups"
Advisor: László Babai

Lide Li, Ph.D. 1993
Thesis: "On the Counting Functions"
Advisor: Lance Fortnow

Katalin Friedl, Ph.D. 1994, currently at the Hungarian Academy of Sciences
Thesis: "Decomposition of Matrix Groups and Algebras"
Advisor: László Babai

Chun-Kuen Ho, Ph.D. 1994
Thesis: "Convergence in Recursive Analysis"
Advisor: Stuart Kurtz

Barun Chandra, Ph.D. 1994, currently at University of New Haven
Thesis: "Approximation and Online Algorithms for Graph Problems"
Advisor: Howard Karloff

John D. Rogers, Ph.D. 1995, currently at DePaul University, Chicago
Thesis: "Isomorphisms, Separability, and One-Way Functions"
Advisor: Stuart Kurtz

Anna Gál, Ph.D. 1995, currently at the University of Texas at Austin
Thesis: "Resource Efficient Self-Stabilizing Systems"
Advisors: Janos Simon, László Babai

Chengdian Lin, Ph.D. 1995
Thesis: "Combinatorial Methods in Boolean Function Complexity"
Advisor: Janos Simon

Shi-Chun Tsai, Ph.D. 1996, currently at National Chiao Tung University, Taiwan
Thesis: "Algebraic Methods for Pseudorandomness and Boolean Complexity"
Advisor: Janos Simon

Satyanarayana V. Lokam, Ph.D. 1996, currently at Microsoft Research, India
Thesis: "Algebraic and Combinatorial Methods in Computational Complexity Theory"
Advisor: László Babai

Steven Crocker, Ph.D. 1997
Thesis: "The Incremental Approach in 3-D Graphics"
Advisor: Ketan Mulmuley

Peter Kimmel, Ph.D. 1997, currently at Northeastern Illinois University
Thesis: "Communication Complexity"
Advisor: László Babai

Sophie Laplante, Ph.D. 1997, currently at the Universite Paris Sud - XI (Orsay)
Thesis: "Kolmogorov Techniques in Computational Complexity Theory"
Advisor: Lance Fortnow

Amber Settle, Ph.D. 1999, currently at DePaul University, Chicago
Thesis: "New Bounds for the Distributed Firing Synchronization Problem"
Advisor: Janos Simon

Marcus Schaefer, Ph.D. 1999, currently at DePaul University, Chicago
Thesis: "Completeness and Incompleteness"
Advisor: Stuart Kurtz

Dieter Van Melkebeek, Ph.D. 1999, currently at the University of Wisconsin-Madison
Thesis: "Randomness and Completeness in Computational Complexity"
Advisor: Lance Fortnow

Pradyut Shah, Ph.D. 2001, currently at Morgan Stanley, New York
Thesis: "Lower Bounds for Parallel Algorithms"
Advisor: Ketan Mulmuley

Samuel "Sandy" Kutin, Ph.D. 2002, currently at the Institute for Defense Analyses
Thesis: "Algorithmic Stability and Ensemble-Based Learning"
Advisors: Partha Niyogi, László Babai

Thomas Hayes, Ph.D. 2003, currently at the University of New Mexico, Albuquerque
Thesis: "Rapidly Mixing Markov Chains for Graph Colorings"
Advisors: Eric Vigoda, László Babai

Rahul Santhanam, Ph.D. 2005, currently at University of Edinburgh
Thesis: "Hierarchy Theorems and Resource Tradeoffs for Semantic Classes"
Advisors: Lance Fortnow, Janos Simon

Daniel Štefankovič, Ph.D. 2005, currently at the University of Rochester
Thesis: "Algorithms for Simple Curves on Surfaces, String Graphs and Crossing Numbers"
Advisor: László Babai

Ivona Bezáková, Ph.D. 2006, currently at the Rochester Institute of Technology
Thesis: "Faster Markov Chain Monte Carlo Algorithms for the Permanent and Binary Contingency Tables"
Advisor: Eric Vigoda

Murali Krishnan Ganapathy, Ph.D. 2006, currently at Google, Inc
Thesis: "Robust Mixing"
Advisor: László Babai

Kenneth Harris, Ph.D. 2007, currently at the University of Michigan
Thesis: "The Effective Content of Classical Theorems on Saturated Models"
Advisor: Robert Soare

Varsha Dani, Ph.D. 2007
Thesis: "Algorithms for Bandit Online Linear Optimization"
Advisor: Lance Fortnow

Sourav Chakraborty, Ph.D. 2008, currently at the Technion, Haifa
Thesis: "Models of Query Complexity for Boolean Functions"
Advisor: László Babai

Linda Sellie, Ph.D. 2008
Thesis: "Learning Random DNF over the Uniform Distribution"
Advisor: Stuart Kurtz

Hariharan Narayanan, Ph.D. 2009, currently at MIT
Thesis: "Diffusion in Computer Science and Statistics"
Advisor: Partha Niyogi

Raghav Kulkarni, Ph.D. 2010, currently at LIAFA Paris 7 and LRI Paris 11, France
Thesis: "Computational Complexity: Counting, Evasiveness, and Isolation"
Advisors: Janos Simon, Alexander Razborov

Paolo Codenotti, Ph.D. 2011, currently at Institute for Mathematics and its Applications
Thesis: "Testing Isomorphism of Combinatorial and Algebraic Structures"
Advisor: László Babai

Joshua Grochow, Ph.D. 2012, currently at University of Toronto
Thesis: " Symmetry and Equivalence Relations in Classical and Geometry Complexity Theory"
Advisors: Lance Fortnow, Ketan Mulmuley

Parinya Chalermsook, Ph.D. 2012, currently at Max-Planck-Institut fur Informatik, Saarbrucken
Thesis: "Approximation Algorithms for integral Concurrent Flow, Independent Set of Rectangles, and Fire Containment Problems"
Advisors: Janos Simon, Julia Chuzhoy

Pratik Worah, Ph.D. 2013, currently at New York University
Thesis: "Approximation Resistance in Optimization Hierarchies: Beyond Linear Predicates"
Advisor: Janos Simon

Pooya Hatami, Ph.D. 2015, currently at IAS
Thesis: "Higher-Order Fourier Analysis over Finite Fields and Applications"
Advisors: Alexander Razborov, Madhur Tultsiani

Denis Pankratov, Ph.D. 2015, currently at University of Toronto
Thesis: "Communication Complexity and Information Complexity"
Advisor: László Babai

Theory researchers who spent part of their graduate studies in our Department

Vince Grolmusz, currently at Eötvös University, Budapest, Hungary

Robert Szelepcsényi

Mathematics PhDs advised by the theory group

Lajos Rónyai, Ph.D. 1987, currently at the Technical University, Budapest, Hungary
Thesis: "Complexity of Algebras"
Advisor: László Babai

Gábor Tardos, Ph.D. 1988, currently at the Hungarian Academy of Science, Budapest
Thesis: "Constructions in Universal Algebra"
Advisor: László Babai

Albert Goodman, Ph.D. 1992, currently at the University of Missouri at Rolla
Thesis: "Automorphism Groups of Graphs: Asymptotic Problems"
Advisor: László Babai

Barry Guiduli, Ph.D. 1996, currently at Morgan Stanley, New York
Thesis: "Spectral Extrema for Graphs"
Advisor: László Babai

Mikhail Belkin, Ph.D. 2003, currently at The Ohio State University
Thesis: "Problems of Learning on Manifolds"
Advisor: Partha Niyogi

Evelina Toumpakari, Ph.D. 2005, currently at Columbia College, Chicago
Thesis: "On the Abelian Sandpile Model"
Advisors: László Babai, Steve Lalley

Aytek Erdil, Ph.D. 2006, currently at Harvard Business School
Thesis: "Two-sided matching with ties"
Advisors: Roger Myerson, László Babai