Theory Group, Department of Computer Science, University of Chicago




Theory PhDs awarded in the Department

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

Mario Szegedy, Ph.D. 1989, currently at Rutgers University
        Thesis title: "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 title: "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 title: "Chains, Gaps, and Genericity: Three Topics in Structural Complexity"
        Advisor: Stuart Kurtz

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Samuel "Sandy" Kutin, Ph.D. 2002, currently at the Institute for Defense Analyses
        Thesis title: "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 title: "Rapidly Mixing Markov Chains for Graph Colorings"
        Advisors: Eric Vigoda, László Babai

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

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

Ivona Bezáková, Ph.D. 2006, currently at Rochester Institute of Technology
        Thesis title: "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 title: "Robust Mixing"
        Advisor: László Babai

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

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

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

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

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

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

Vince Grolmusz, currently at the 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 title: "Complexity of Algebras"
        Advisor: László Babai

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

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

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

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

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

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