|
|
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.
Teaching Awards
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
|