Nagroda Goedla

Nagroda Goedla (Goedel Prize)

Wyróżnienie przyznawane od 1993 r. autorom wybitnych prac w dziedzinie informatyki teoretycznej, wspólnie przez dwie instytucje: European Association for Theoretical Computer Science (EATCS) oraz Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM-SIGACT). Patronem Nagrody jest wybitny matematyk austriacki Kurt Goedel.

Nagroda jest wyrazem uznania dla konkretnych prac badawczych, nie jest przyznawana za całokształt osiągnięć. Towarzyszy jej premia w wysokości 5 tys. USD.

Wybrani laureaci:

1993 - Laszlo Babai, Shafi Goldwasser – za pracę Arthur-Merlin games: a randomized proof system and a hierarchy of complexity classes
Silvio Micali, Shlomo Moran, Charles Rackoff – za pracę The knowledge complexity of interactive proof systems

1995 - Neil Immerman – za pracę Nondeterministic space is closed under complementation
Robert Szelepcsenyi – za pracę The method of forced enumeration for nondeterministic automata

1998 - Seinosuke Toda – za artykuł PP is as Hard as the Polynomial-Time Hierarchy

2001 - Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, Laszlo Lovasz, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy – za 3 prace: Interactive Proofs and the Hardness of Approximating Cliques Probabilistic Checking of Proofs: A New Characterization of NP Proof Verification and the Hardness of Approximation Problems