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 cenyRok Meno/mená Dôvod1993 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 automatov2001 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ému2011 Johan Håstad  za zavedenie nových analytických metód v teórii aproximácie obťažnosti pri výpočte problémov2012  Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen  každý za základný článok o algoritmické teórii hier2013Dan Boneh, Matthew K. Franklin a Antoine Joux2014Ronald Fagin, Amnon Lotem a Moni Naor2015Daniel Spielman, Shang-Hua Teng2016Stephen Brookes a Peter W. O’Hearn2017Cynthia Dwork, Frank McSherry, Kobbi Nissim, a Adam D. Smith2018Oded Regev2019Irit Dinur2020Robin Moser a Gábor Tardos2021Andrei A. Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer a David Richerby2022Zvika Brakerski, Craig Gentry a Vinod Vaikuntanathan2023Samuel Fiorini, Serge Massar a Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf a Thomas Rothvoss2024Ryan Williams

 Externé odkazy 
Oficiálna stránka ceny

Kategória:Vedecké ocenenia