|
nothing
|
|
Awards
The Gödel Prize for outstanding papers in the area of theoretical computer science
has been awarded annually
since 1993, jointly by the ACM SIGACT and its European counterpart,
the 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: Róbert Szelepcsényi for his paper "The method of forced enumeration for nondeterministic automata," Acta Informatica 26 (1988),
279-284.
- 2001: Uriel Feige, Shafi Goldwasser, Laszlo 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.
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 Gal 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
Last modified: November 11, 2003
A very short paragraph to force Netscape to align things properly.
Hopefully this will work.
A very short paragraph to force Netscape to align things properly.
Hopefully this will work.
A very short paragraph to force Netscape to align things properly.
Hopefully this will work.
|