Gödelova cena

Gödelova cena
Obrázek spojený s cenou
Kurt Gödel v roce 1925
Organizátor EATCS a SIGACT
Datum vzniku 1992

Gödel cena je rozdíl vytvořen v roce 1992 podle Evropské asociace pro teoretické informatiky (EATCS) a Special Interest Group na algoritmech a výpočetní teorii (SIGACT) na sdružení pro výpočetní techniku (ACM) na počest vynikající práci " teoretická věda . Je pojmenován na počest logika Kurta Gödela .

Popis

Gödelova cena se uděluje každoročně od roku 1993 a zahrnuje cenu 5 000  USD . Cena odlišuje položku spíše než jednotlivce. Aby byl článek příjemce způsobilý, musí být v předchozích 14 letech publikován v recenzovaném časopise. Gödelova cena je spolu s Turingovou cenou považována za jednu ze dvou největších mezinárodních cen v oblasti informatiky .

Cena je pojmenována na počest Kurta Gödela za jeho práci v matematické logice a jeho intuici problému P = NP .

Laureáti

Seznam laureátů
Rok Jména Příspěvek
1993 László Babai ( Maďarsko ) a Shlomo Moran ( Izrael ), Shafi Goldwasser ( Izrael / USA ), Silvio Micali ( Itálie / USA ) a Charles Rackoff ( USA ) Vývoj konceptu interaktivního zkušebního systému
1994 Johan Håstad ( Švédsko ) Svorky týkající se problémů s booleovským obvodem , a zejména s paritní funkcí
1995 Neil Immerman ( USA ) a Róbert Szelepcsényi ( Slovensko ) Jejich věta spojující třídy NSPACE a co-NSPACE
1996 Mark Jerrum ( Velká Británie ) a Alistair Sinclair ( Velká Británie ) Jejich práce na Markovových řetězcích a trvalé přiblížení
1997 Joseph Halpern ( USA ) a Yoram Moses ( Izrael ) Vývoj pojmu informace v kontextu distribuovaných systémů
1998 Seinosuke Toda ( Japonsko ) Jeho věta týkající se tříd složitosti PP a PH
1999 Peter Shor ( Spojené státy ) Algoritmus Shor , který umožňuje k číslům faktoru v polynomiálním čase na kvantový počítač
2000 Moshe Vardi ( Izrael ) a Pierre Wolper ( Belgie ) Jejich práce na časové logice v kontextu konečných automatů
2001 Sanjeev Arora ( USA ), Uriel Feige ( Izrael ), Shafi Goldwasser ( Izrael / USA ), Carsten Lund ( Dánsko ), László Lovász ( Maďarsko / USA ), Rajeev Motwani ( Indie ), Shmuel Safra ( Izrael ), Madhu Súdán ( Spojené státy ) a Mario Szegedy ( Maďarsko / Spojené státy ) Jejich věta o PCP
2002 Géraud Sénizergues ( Francie ) Prokázaly Rozhodnutelnost rovnosti dvou jazyků uznávaný deterministické Skládaný automatů
2003 Yoav Freund ( Izrael ) a Robert Schapire ( Spojené státy ) Algoritmus AdaBoost ve strojovém učení
2004 Maurice Herlihy ( USA ), Michael Saks ( USA ), Nir Shavit ( Izrael ), Fotios Zaharoglou ( Řecko ) Aplikace konceptů topologie na distribuované výpočty
2005 Noga Alon ( Izrael ), Yossi Matias ( Izrael ) a Mario Szegedy ( Maďarsko ) Jejich příspěvky k algoritmům dolování datových toků
2006 Manindra Agrawal ( Indie ), Neeraj Kayal ( Indie ) a Nitin Saxena ( Indie ) Test prvosti AKS
2007 Alexandre Razborov ( Rusko ) a Steven Rudich ( Spojené státy ) Jejich klíčový článek o přírodních důkazech
2008 Shang-Hua Teng ( Čína ) a Daniel Spielman ( Spojené státy ) Algoritmus hladký analýza ( vyhlazené analýza )
2009 Omer Reingold ( Izrael ), Salil Vadhan ( USA ) a Avi Wigderson ( Izrael ) Klikatá produkt grafů
2010 Sanjeev Arora ( Spojené státy ) a Joseph SB Mitchell ( Spojené státy ) Polynom aproximace schéma na problém obchodního cestujícího v případě euklidovské
2011 Johan Håstad ( Švédsko ) Výsledky obtížnosti aproximace spojené s teorémem PCP
2012 Elias Koutsoupias ( Řecko ), Christos Papadimitriou ( Řecko ), Noam Nisan ( Izrael ), Amir Ronen ( Izrael ), Tim Roughgarden ( USA ) a Éva Tardos ( Maďarsko ) Tvorba algoritmické teorie her
2013 Dan Boneh ( Izrael ), Matthew K. Franklin ( USA ) a Antoine Joux ( Francie ) Zavedení kryptografie založené na vazbě
2014 Ronald Fagin ( USA ), Amnon Lotem ( Izrael ) a Moni Naor ( Izrael ) Optimální agregační algoritmy
2015 Shang-Hua Teng ( Čína ) a Daniel Spielman ( Spojené státy ) Jejich práce v digitální lineární algebře a aplikace na algoritmy grafů a teorii spektrálních grafů
2016 Stephen D. Brookes ( Spojené království ) a Peter O'Hearn ( Kanada ) Vynález souběžné separační logiky
2017 Cynthia Dwork ( USA ), Frank McSherry ( USA ), Kobbi Nissim ( Izrael ) a Adam D. Smith ( USA ) Vynález rozdílné důvěrnosti
2018 Oded Regev ( Izrael ) Zavedení problému učení s chybami , studium jeho průměrné složitosti redukcí na problémy euklidovských sítí a jeho dopad na postkvantovou kryptografii
2019 Irit Dinur ( Izrael ) Pro důkaz zásadně odlišný od věty PCP , jednodušší, přímější a efektivnější.
2020 Robin A. Moser a Gábor Tardos ( Maďarsko ) Pro algoritmickou verzi Lovászova lokálního lemmatu .
2021 Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer ( Velká Británie ) a David Richerby Klasifikace složitosti počítání  (in) na problémy s omezujícími podmínkami .

Významné články

  1. László Babai a Shlomo Moran , „  Hry Arthur-Merlin: randomizovaný kontrolní systém a hierarchie třídy složitosti  “, Journal of Computer and System Sciences , sv.  36, n O  21988, str.  254–276 ( DOI  10.1016 / 0022-0000 (88) 90028-1 , číst online )
  2. S. Goldwasser , S. Micali a C. Rackoff , „  Znalostní složitost interaktivních důkazních systémů  “, SIAM Journal on Computing , sv.  18, n o  1,1989, str.  186–208 ( DOI  10.1137 / 0218012 , číst online )
  3. Johan Håstad , „Téměř optimální dolní hranice pro malé hloubkové obvody“ , Silvio Micali (editor), Randomness and Computation , JAI Press, kol.  „Advances in Computing Research“ ( n O  5),1989( ISBN  0-89232-896-7 , číst online [ archiv22. února 2012] ), „Téměř optimální dolní hranice pro obvodysmalou hloubkou“,s.  6–20
  4. Neil Immerman , „  Nedeterministický prostor je uzavřen doplňováním,  “ SIAM Journal on Computing , roč.  17, n o  5,1988, str.  935–938 ( ISSN  1095-7111 , DOI  10.1137 / 0217058 , číst online )
  5. R. Szelepcsényi , „  Metoda vynuceného výčtu nedeterministických automatů  “, Acta Informatica , sv.  26, n o  3,1988, str.  279–284 ( DOI  10.1007 / BF00299636 )
  6. Mark Jerrum a Alistair Sinclair , „  Aproximace stálého  “, SIAM Journal on Computing , roč.  18, n o  6,1989, str.  1149–1178 ( ISSN  1095-7111 , DOI  10.1137 / 0218077 )
  7. Alistair Sinclair a Mark Jerrum , „  Přibližné počítání, rovnoměrné generování a rychlé míchání Markovových řetězců  “, Information and Computation , sv.  82, n o  1,1989, str.  93–133 ( DOI  10.1016 / 0890-5401 (89) 90067-9 )
  8. Joseph Halpern a Yoram Moses , „  Znalosti a obecné znalosti v distribuovaném prostředí,  “ Journal of ACM , vol.  37, n o  3,1990, str.  549–587 ( DOI  10.1145 / 79147.79161 )
  9. Seinosuke Toda , „  PP je stejně tvrdý jako hierarchie polynomiálního času  “, SIAM Journal on Computing , roč.  20, n o  5,1991, str.  865–877 ( DOI  10.1137 / 0220053 , číst online )
  10. Peter W. Shor , „  Algoritmy polynomiálního času pro Prime Factorization a diskrétní logaritmy na kvantovém počítači  “, SIAM Journal on Computing , sv.  26, n o  5,1997, str.  1484–1509 ( DOI  10.1137 / S0097539795293172 , číst online )
  11. Moshe Y. Vardi a Pierre Wolper , „  Důvod k nekonečným výpočtům  “, Information and Computation , sv.  115, n o  1,1994, str.  1–37 ( DOI  10.1006 / inco.1994.1092 , číst online [ archiv25. srpna 2011] )
  12. Uriel Feige , Shafi Goldwasser , Laszlo Lovász , Shmuel Safra a Mario Szegedy , „  Interaktivní důkazy a tvrdost přibližných klik  “, Journal of ACM , sv.  43, n O  21996, str.  268–292 ( DOI  10.1145 / 226643.226652 , číst online )
  13. Sanjeev Arora a Shmuel Safra , „  Pravděpodobnostní kontrola důkazů: nová charakteristika NP  “, Journal of ACM , sv.  45, n o  1,1998, str.  70–122 ( DOI  10.1145 / 273865.273901 , číst online [ archiv10. června 2011] )
  14. Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Súdán a Mario Szegedy , „  Ověřování důkazů a tvrdost problémů s aproximací  “, Journal of ACM , sv.  45, n o  3,1998, str.  501–555 ( DOI  10.1145 / 278298.278306 , číst online [ archiv10. června 2011] )
  15. Géraud Sénizergues , „  L (A) = L (B)? rozhodovatelnost vyplývá z úplných formálních systémů  “, Theor. Comput. Sci. , sv.  251 n o  12001, str.  1–166 ( DOI  10.1016 / S0304-3975 (00) 00285-1 )
  16. Y. Freund a RE Schapire , „  Rozhodnutí-teoretické zobecnění on-line učení a aplikace na podporu  “, Journal of Computer and System Sciences , sv.  55, n o  1,1997, str.  119–139 ( DOI  10.1006 / jcss.1997.1504 , číst online )
  17. Maurice Herlihy a Nir Shavit, „  Topologická struktura asynchronního výpočtu  “, Journal of ACM , sv.  46, n O  6,1999, str.  858–923 ( DOI  10.1145 / 331524.331529 , číst online )
  18. Michael Saks a Fotios Zaharoglou , „  Dohoda k -set bez čekání je nemožná: topologie veřejného poznání  “, SIAM Journal on Computing , sv.  29, n o  5,2000, str.  1449–1483 ( DOI  10.1137 / S0097539796307698 )
  19. Noga Alon , Yossi Matias a Mario Szegedy , „  Prostorová složitost aproximace frekvenčních momentů  “, Journal of Computer and System Sciences , sv.  58, n o  1,1999, str.  137–147 ( DOI  10.1006 / jcss.1997.1545 , číst online )
  20. Manindra Agrawal, Neeraj Kayal a Nitin Saxena, „  PRIMES je v P  “, Annals of Mathematics , sv.  160, n O  22004, str.  781–793 ( DOI  10.4007 / annals.2004.160.781 , číst online [ archiv7. června 2011] )
  21. Alexander A. Razborov a Steven Rudich , "  Přírodní důkazy  ", Journal of Computer a systémových věd , vol.  55, n o  1,1997, str.  24–35 ( DOI  10.1006 / jcss.1997.1494 )
  22. Daniel A. Spielman a Shang-Hua Teng , „  Hladká analýza algoritmů: Proč simplexní algoritmus obvykle trvá polynomiální čas  “, Journal of the ACM , vol.  51, n o  3,2004, str.  385–463 ( číst online [ archiv6. prosince 2009] )
  23. Omer Reingold , Salil Vadhan a Avi Wigderson , „  Entropické vlny, produkt grafu cik-cak a nové expandéry konstantního stupně  “, Annals of Mathematics , sv.  155, n o  1,2002, str.  157–187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Math Reviews  1888797 , číst online [ archiv7. prosince 2009] )
  24. Omer Reingold , „  Neusměrněná konektivita v logovém prostoru,  “ Journal of the ACM , vol.  55, n O  4,2008, str.  1–24 ( číst online )
  25. Sanjeev Arora , „  Schémata polynomiálního přibližování času pro euklidovského obchodního cestujícího a další geometrické problémy  “, Journal of ACM , sv.  45, n o  5,1998, str.  753–782 ( DOI  10.1145 / 290179.290180 )
  26. Joseph SB Mitchell , „  Gilotinové členění Přibližné polygonální členění: Jednoduché schéma aproximace v polynomiálním čase pro geometrické TSP, k-MST a související problémy  “, SIAM Journal on Computing , sv.  28, n O  4,1999, str.  1298–1309 ( ISSN  1095-7111 , DOI  10.1137 / S0097539796309764 )
  27. Johan Håstad , „  Některé optimální výsledky přibližnosti  “, Journal of ACM , sv.  48,2001, str.  798–859 ( DOI  10.1145 / 502090.502098 , číst online )
  28. Elias Koutsoupias a Christos Papadimitriou , „  Worst-case equilibria  “, Computer Science Review , roč.  3, n o  22009, str.  65–69 ( DOI  10.1016 / j.cosrev.2009.04.003 )
  29. Tim Roughgarden a Éva Tardos : „  Jak špatné je sobecké směrování?  ”, Journal of the ACM , vol.  49, n O  22002, str.  236–259 ( DOI  10.1145 / 506147.506153 )
  30. Noam Nisan a Amir Ronen , „  Algorithmic Mechanism Design  “, Hry a ekonomické chování , sv.  35, n kost  1-2,2001, str.  166–196 ( DOI  10.1006 / hra.1999.0790 )
  31. Dan Boneh a Matthew Franklin , „  Šifrování založené na identitě z Weilova párování,  “ SIAM Journal on Computing , sv.  32, n o  3,2003, str.  586–615 ( DOI  10.1137 / S0097539701398521 , matematické recenze  2001745 )
  32. Antoine Joux , „  Jednostranný protokol pro tripartitu Diffie-Hellman  “, Journal of Cryptology , sv.  17, n O  4,2004, str.  263–276 ( DOI  10.1007 / s00145-004-0312-y , matematické recenze  2090557 )
  33. Ronald Fagin , Amnon Lotem a Moni Naor , „  Optimální agregační algoritmy pro middleware  “, Journal of Computer and System Sciences , sv.  66, n O  4,2003, str.  614-656 ( DOI  10.1016 / S0022-0000 (03) 00026-6 )
  34. Daniel A. Spielman a Shang-Hua Teng , „  Spectral Sparsification of Graphs  “, SIAM Journal on Computing , roč.  40, n O  4,2011, str.  981-1025 ( ISSN  0097-5397 , DOI  10.1137 / 08074489X ).
  35. Daniel A. Spielman a Shang-Hua Teng , „  Algoritmus lokálního klastrování pro masivní grafy a jeho aplikace pro téměř lineární dělení časových grafů  “, SIAM Journal on Computing , sv.  42, n o  1,2013, str.  1-26 ( ISSN  0097-5397 , DOI  10.1137 / 080744888 ).
  36. Daniel A. Spielman a Shang-Hua Teng , „  Téměř lineární časové algoritmy pro předpřipravování a řešení symetrických, šikmo dominujících lineárních systémů  “, SIAM Journal on Matrix Analysis and Applications , sv.  35, n o  3,2014, str.  835-885 ( ISSN  0895-4798 , DOI  10.1137 / 090771430 ).
  37. Peter W. O'Hearn, „  Zdroje, souběžnost a místní uvažování  “, Theoretical Computer Science , sv.  375, n kost  1-3, 2007, str.  271-307.
  38. Stephen Brookes, „  Sémantika pro logiku souběžné separace,  “ Theoretical Computer Science , sv.  375, n kost  1-3, 2007, str.  227-270.
  39. Cynthia Dwork, Frank McSherry, Kobbi Nissim a Adam Smith, „  Kalibrace šumu na citlivost  “, Soukromý datový analytický deník soukromí a důvěrnosti , sv.  7, n o  3,2016.
  40. (in) Oded Regev , „  We lattices, learning with errors, random linear codes and cryptography  “ , Journal of the ACM , vol.  56, n O  6, 2009, str.  34: 1-34: 40 ( DOI  10.1145 / 1568318.1568324 ).
  41. (in) Irit Dinur , „  The PCP theorem by amplification gap  “ , Journal of the ACM , vol.  54, n o  3, 2007, str.  12
  42. (in) Robin A. Moser a Gábor Tardos , „  konstruktivní Důkaz obecné Lovász Local Lemma  “ , Journal of ACM , sv.  57, n O  2 2010, str.  11: 1--11: 15
  43. Andrei A. Bulatov, „  Složitost problému spokojenosti s počítáním omezení  “, Journal of ACM , Association for Computing Machinery (ACM), sv.  60, n o  5,2013, str.  1–41 ( ISSN  0004-5411 , DOI  10.1145 / 2528400 )
  44. Martin Dyer a David Richerby , „  Efektivní dichotomie pro problém spokojenosti s počítáním omezení  “, Společnost pro průmyslovou a aplikovanou matematiku (SIAM) , sv.  42, n o  3, 2013, str.  1245–1274 ( ISSN  0097-5397 , DOI  10.1137 / 100811258 )
  45. Jin-Yi Cai a Xi Chen, „  Složitost počítání CSP s komplexními váhami  “, Association for Computing Machinery (ACM) , sv.  64, n o  3, 22. června 2017, str.  1–39 ( ISSN  0004-5411 , DOI  10.1145 / 2822891 )

Poznámky

Poznámky

  1. První odstavce cenové stránky
  2. Jacques Stern , "  Antoine Joux, cena Gödel 2013  ", 1024 - Bulletin IT společnosti Francie , n o  1,září 2013, str.  107-110 ( číst online )
  3. Na webových stránkách EATCS: Cena je pojmenována na počest Kurta Gödela jako uznání jeho hlavních příspěvků k matematické logice a jeho zájmu, které byly objeveny v dopise, který krátce před Neumannovou smrtí napsal Johnovi von Neumannovi, v čem se stal slavný “ Otázka P versus NP.
  4. Oficiální oznámení o Godlově ceně za rok 2014 .
  5. Článek o článku a ceně: Thore Husfeldt, „  Osobní realita (Gödelova cena 2014)  “ [ archiv du4. května 2015] ,2014(zpřístupněno 30. dubna 2015 ) .
  6. „  Cena Gödel za rok 2015  “ , SIGACT
  7. „  Cena Gödel 2016  “ , na EATCS
  8. „  Cena Gödel za rok 2017  “ , na EATCS .
  9. „  Citace Gödelovy ceny do roku 2021  “
(fr) Tento článek je částečně nebo zcela převzat z článku Wikipedie v angličtině s názvem „  Gödelova cena  “ ( viz seznam autorů ) .

Podívejte se také

Související článek

externí odkazy