Gödelova cena je vedecké ocenenie udeľované každoročne od roku 1993 za najlepšie vedecké články z oblasti teoretickej informatiky. Cena je pomenovaná po rakúskom matematikovi a logikovi Kurtovi Gödelovi a udeľujú ju asociácie EATCS (European Association for Theoretical Computer Science) a ACM SIGACT (Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory). Súčasťou ceny je finančná odmena vo výške 5000 amerických dolárov.
Nositelia ceny
| Rok |
Meno/mená |
Dôvod |
| 1993 |
László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran a Charles Rackoff |
za vývoj interaktívnych dôkazových systémov. |
| 1994 |
Johan Håstad |
za exponenciálny dolný odhad zložitosti Booleovských okruhov s konštantnou hĺbkou. |
| 1995 |
Neil Immerman a Róbert Szelepcsényi |
za Immermanovu-Szelepcsényiho vetu o uzavretosti triedy kontextových jazykov na komplement. |
| 1996 |
Mark Jerrum a Alistair Sinclair |
za prácu v oblasti markovovských reťazcov. |
| 1997 |
Joseph Halpern a Yoram Moses |
za definíciu formálneho pojmu "poznatok" v distribuovaných systémoch . |
| 1998 |
Seinosuke Toda |
za Todovu vetu, ktorá ukázala súvislosť medzi PP a PH zložitosťou. |
| 1999 |
Peter Shor |
za Shorov algoritmus na faktorizáciu čísel v polynomiálnom čase na kvantovom počítači . |
| 2000 |
Moshe Y. Vardi a Pierre Wolper |
za prácu v oblasti overovania modelov pomocou konečných automatov |
| 2001 |
Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Radžív Mótvání, Shmuel Safra, Madhu Sudan a Mario Szegedy |
za PCP vetu a jej aplikácie v oblasti zložitosti aproximácie. |
| 2002 |
Géraud Sénizergues |
za dôkaz, že problém ekvivalencie deterministických zásobníkových automatov je rozhodnuteľný. |
| 2003 |
Yoav Freund a Robert Schapire |
za algoritmus AdaBoost. |
| 2004 |
Maurice Herlihy, Mike Saks, Nir Shavit a Fotios Zaharoglou |
za aplikáciu topológie v teórii distribuovaných výpočtov. |
| 2005 |
Noga Alon, Yossi Matias a Mario Szegedy |
za základné výsledky v oblasti algoritmov na údajových prúdoch (streamoch). |
| 2006 |
Maníndra Agravál, Neeraj Kayal a Nitin Saxena |
za test prvočíselnosti AKS. |
| 2007 |
Aleksandr Aleksandrovič Razborov a Steven Rudich |
za tzv. prirodzené dôkazy. |
| 2008 |
Shanghua Teng a Daniel Spielman |
za tzv. zjemnenú analýzu algoritmov. |
| 2009 |
Omer Reingold, Salil Vadhan a Avi Wigderson |
za tzv. zig-zag súčin grafov. |
Externé odkazy [upraviť]
