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.
2010 Sanjeev Arora a Joseph S. B. Mitchell za algoritmus pre riešenie eukleidovského problému
2011 Johan Håstad za zavedenie nových analytických metód v teórii aproximácie obťažnosti pri výpočte problémov
2012 Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen každý za základný článok o algoritmické teórii hier

Externé odkazy

upraviť