# 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