Gödelova cena

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	Alexandr Alexandrovič 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
2013	Dan Boneh, Matthew K. Franklin a Antoine Joux
2014	Ronald Fagin, Amnon Lotem a Moni Naor
2015	Daniel Spielman, Shang-Hua Teng
2016	Stephen Brookes a Peter W. O’Hearn
2017	Cynthia Dwork, Frank McSherry, Kobbi Nissim, a Adam D. Smith
2018	Oded Regev
2019	Irit Dinur
2020	Robin Moser a Gábor Tardos
2021	Andrei A. Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer a David Richerby
2022	Zvika Brakerski, Craig Gentry a Vinod Vaikuntanathan
2023	Samuel Fiorini, Serge Massar a Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf a Thomas Rothvoss
2024	Ryan Williams

Externé odkazy

• Oficiálna stránka ceny