Theory Group

Department of Computer Science The University of Chicago

Home Faculty Current Students Former Students Awards Join Us Other Theory Groups in Chicago Miscellaneous

Awards

Rolf Nevanlinna Prize, International Mathematical Union

• 1990: Alexander Razborov for his work on lower bounds in circuit complexity.

Gödel Prize, ACM SIGACT and EATCS

• 1993: László Babai and Shlomo Moran for their paper "Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes," Journal of Computer and System Sciences, 36 (1988), 254-276.
• 1995: Robert Szelepcsényi for his paper "The method of forced enumeration for nondeterministic automata," Acta Informatica 26 (1988), 279-284.
• 2001: Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy, for their paper "Interactive Proofs and the Hardness of Approximating Cliques," Journal of the ACM 43 (1996), 268-292.
• 2001: Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy for their paper "Proof Verification and the Hardness of Approximation Problems," Journal of the ACM 45 (1998), 501-555.
• 2005: Noga Alon, Yossi Matias, and Mario Szegedy for their paper "The Space Complexity of Approximating the Frequency Moments," Journal of Computer and System Sciences 58 (1999), 137-147.
• 2007: Alexander Razborov and Steven Rudich for their paper "Natural Proofs," Journal of Computer and System Sciences 55 (1997), 24-35.

David P. Robbins Prize, American Mathematical Society

• 2013: Alexander Razborov for his work on flag algebras.

Teaching Awards

• 1994: John Rogers, Wayne C. Booth Graduate Student Prize for Excellence in Teaching
• 2005: László Babai, Quantrell Award for Excellence in Undergraduate Teaching
• 2005: Ken Harris, Wayne C. Booth Graduate Student Prize for Excellence in Teaching
• 2007: Eric Purdy, University of Chicago Graduate Student Sciences Teaching Prize
• 2008: Janos Simon, Quantrell Award for Excellence in Undergraduate Teaching
• 2009: Stuart Kurtz, Quantrell Award for Excellence in Undergraduate Teaching
• 2009: Joshua Grochow, Teaching Assistant Prize
• 2013: Pooya Hatami, Teaching Assistant Prize

ACM: Doctoral Dissertation Award

• Dieter van Melkebeek for his dissertation "Randomness and Completeness in Computational Complexity," 1999
• Carsten Lund, Doctoral Dissertation Series Winner for his dissertation "The Power of Interaction," 1991
• Ketan D. Mulmuley for his dissertation "Full Abstraction and Semantic Equivalence," 1986

Machtey Best Student Paper Award, IEEE Symposium on Foundations of Computer Science (FOCS)

• Eric Vigoda for his paper "Improved Bounds for Sampling Colorings," 1999
• Satyanarayana V. Lokam for his paper "Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity," 1995
• Anna Gál for her paper "Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates," 1991

Danny Lewin Best Student Paper Award, ACM Symposium on Theory of Computing (STOC)

• Thomas P. Hayes for his paper "Randomly Coloring Graphs of Girth At Least Five," 2003

Ronald V. Book Prize for Best Student Paper, Computational Complexity Conference

• Marcus Schaefer for his paper "Graph Ramsey Theory and the Polynomial Hierarchy," 1999
• Dieter Van Melkebeek for his paper "Reducing P to a Sparse Set Using a Constant Number of Queries Collapses P to L," 1996
• John Rogers for his paper "The Isomorphism Conjecture Holds and One-Way Functions Exist Relative to an Oracle," 1995