Gödel-díj

Gödel-díj
A díjhoz kapcsolódó kép
Kurt Gödel 1925-ben
Szervező EATCS és SIGACT
Létrehozás dátuma 1992

A Gödel-díj az Európai Elméleti Számítástudományi Szövetség (EATCS) és a Számítástechnikai Szövetség (ACM) algoritmusokkal és számítási elmélettel foglalkozó különleges érdekcsoport (SIGACT) által 1992- ben létrehozott megkülönböztetés az „ elméleti számítógép ” kiemelkedő munkájának tiszteletére tudomány . Kurt Gödel logikus tiszteletére nevezték el .

Leírás

A Gödel-díjat 1993 óta évente adják ki, és 5000 USD díjat tartalmaz  . Az ár inkább egy elemet különböztet meg, mint egyént. A jogosultság megszerzéséhez a címzett cikkét az előző 14 évben egy szakértői folyóiratban kell közzétenni. A Gödel-díjat a Turing-díj mellett a két legnagyobb nemzetközi számítástechnikai díj egyikének tartják .

A díjat Kurt Gödel tiszteletére kapta, matematikai logikai munkájáért és a P = NP probléma megérzéséért .

Díjasok

A díjazottak listája
Év Név (ek) Hozzájárulás (ok)
1993 Babai László ( Magyarország ) és Shlomo Moran ( Izrael ), Shafi Goldwasser ( Izrael / Egyesült Államok ), Silvio Micali ( Olaszország / Egyesült Államok ) és Charles Rackoff ( Egyesült Államok ) Az interaktív bizonyítási rendszer koncepciójának kidolgozása
1994 Johan Håstad ( svéd ) Terminálok a logikai áramkör problémáira , és különösen a paritásfüggvényre
1995 Neil Immerman ( Egyesült Államok ) és Szelepcsényi Róbert ( Szlovákia ) Az NSPACE és a társ-NSPACE osztályokat összekapcsoló tételük
1996 Mark Jerrum ( Egyesült Királyság ) és Alistair Sinclair ( Egyesült Királyság ) A Markov-láncokkal kapcsolatos munkájuk és az állandó közelítés
1997 Joseph Halpern ( Egyesült Államok ) és Yoram Moses ( Izrael ) Az információ fogalmának fejlesztése az elosztott rendszerek kontextusában
1998 Seinosuke Toda ( Japán ) Tétele a PP és PH komplex osztályokra vonatkozik
1999 Peter Shor ( Egyesült Államok ) A Shor algoritmus , amely lehetővé teszi a számok tényezőinek polinomiális időbeli meghatározását egy kvantum számítógépen
2000 Moshe Vardi ( Izrael ) és Pierre Wolper ( Belgium ) Munkájuk az időbeli logikáról a véges automaták összefüggésében
2001 Sanjeev Arora ( Egyesült Államok ), Uriel Feige ( Izrael ), Shafi Goldwasser ( Izrael / Egyesült Államok ), Carsten Lund ( Dánia ), Lovász László ( Magyarország / Egyesült Államok ), Rajeev Motwani ( India ), Shmuel Safra ( Izrael ), Madhu Szudán ( Egyesült Államok ) és Mario Szegedy ( Magyarország / Egyesült Államok ) Az PCP-tétel
2002 Géraud Sénizergues ( Franciaország ) Bizonyították eldönthetőség az egyenlőség két nyelv által elismert determinisztikus Egymásra automaták
2003 Yoav Freund ( Izrael ) és Robert Schapire ( Egyesült Államok ) Az AdaBoost algoritmus a gépi tanulásban
2004 Maurice Herlihy ( Egyesült Államok ), Michael Saks ( Egyesült Államok ), Nir Shavit ( Izrael ), Fotios Zaharoglou ( Görögország ) Az alkalmazás a topológia fogalmak az elosztott számítási
2005 Noga Alon ( Izrael ), Yossi Matias ( Izrael ) és Mario Szegedy ( Magyarország ) Hozzájárulásuk az adatáramlás-bányászati ​​algoritmusokhoz
2006 Manindra Agrawal ( India ), Neeraj Kayal ( India ) és Nitin Saxena ( India ) Az AKS elsődleges teszt
2007 Alexandre Razborov ( Oroszország ) és Steven Rudich ( Egyesült Államok ) Alapvető cikkük a természetes bizonyítékról
2008 Shang-Hua Teng ( Kína ) és Daniel Spielman ( Egyesült Államok ) A sima elemzési algoritmus ( sima elemzés )
2009 Omer Reingold ( Izrael ), Salil Vadhan ( Egyesült Államok ) és Avi Wigderson ( Izrael ) A grafikonok cikk-cakk terméke
2010 Sanjeev Arora ( Egyesült Államok ) és Joseph SB Mitchell ( Egyesült Államok ) A polinom közelítő séma az utazó ügynök probléma az euklideszi esetben
2011 Johan Håstad ( svéd ) A közelítés nehézségének eredményei , a PCP-tételhez kapcsolódva
2012 Elias Koutsoupias ( görög ), Christos Papadimitriou ( görög ), Noam Nisan ( Izrael ), Amir Ronen ( Izrael ), Tim Roughgarden ( Egyesült Államok ) és Tardos Éva ( Magyarország ) Az algoritmikus játékelmélet megalkotása
2013 Dan Boneh ( Izrael ), Matthew K. Franklin ( Egyesült Államok ) és Antoine Joux ( Franciaország ) A kapcsolás alapú rejtjelezés bevezetése
2014 Ronald Fagin ( Egyesült Államok ), Amnon Lotem ( Izrael ) és Moni Naor ( Izrael ) Optimális összesítési algoritmusok
2015 Shang-Hua Teng ( Kína ) és Daniel Spielman ( Egyesült Államok ) Munkájuk digitális lineáris algebrában, alkalmazásuk grafikonalgoritmusokhoz és spektrális gráfelméletekhez
2016 Stephen D. Brookes ( Egyesült Királyság ) és Peter O'Hearn ( Kanada ) Az egyidejű elválasztási logika feltalálása
2017 Cynthia Dwork ( Egyesült Államok ), Frank McSherry ( Egyesült Államok ), Kobbi Nissim ( Izrael ) és Adam D. Smith ( Egyesült Államok ) A differenciált titoktartás feltalálása
2018 Oded Regev ( Izrael ) A hibás tanulás problémájának bevezetése, átlagosan annak komplexitásának vizsgálata az euklideszi hálózatok problémáira való redukcióval , valamint a kvantum utáni rejtjelezésre gyakorolt ​​hatása
2019 Irit Dinur ( Izrael ) A PCP-tételtől alapvetően eltérő bizonyítás érdekében egyszerűbb, közvetlenebb és hatékonyabb.
2020 Robin A. Moser és Tardos Gábor ( Magyarország ) Lovász helyi lemmájának algoritmikus változatához .
2021 Andrei Bulatov, Jin-Yi Cai, Xi Chen, Martin Dyer ( Egyesült Királyság ) és David Richerby A megszámlálási komplexitás  osztályozása (a) a kényszer elégedettségi problémáin .

Kiváló cikkek

  1. László Babai és Shlomo Moran „  Arthur-Merlin-játék: egy randomizált bizonyítási rendszert és hierarchiát bonyolultsági osztály  ”, Journal of Computer and System Sciences , vol.  36, n o  21988, P.  254–276 ( DOI  10.1016 / 0022-0000 (88) 90028-1 , online olvasás )
  2. S. Goldwasser , S. Micali és C. Rackoff „  A tudás összetettsége interaktív bizonyítási rendszerek  ”, SIAM Journal on Computing , vol.  18, n o  1,1989, P.  186–208 ( DOI  10.1137 / 0218012 , online olvasás )
  3. Johan Håstad , „Kis mélységű áramkörök majdnem optimális alsó határai ” , Silvio Micali (szerkesztő), Randomness and Computation , JAI Press, coll.  „Advances in Computing Research” ( n o  5),1989( ISBN  0-89232-896-7 , olvasható online [ archívum2012. február 22] ), „Kis mélységű áramkörök majdnem optimális alsó határai”,p.  6–20
  4. Neil Immerman „  determinisztikus tér zárt a  komple ” SIAM Journal on Computing , vol.  17, n o  5,1988, P.  935–938 ( ISSN  1095-7111 , DOI  10.1137 / 0217058 , online olvasás )
  5. Szelepcsényi R. , „  A kényszerszámlálás módszere a nemdeterminisztikus automatákhoz  ”, Acta Informatica , vol.  26, n o  3,1988, P.  279–284 ( DOI  10.1007 / BF00299636 )
  6. Mark Jerrum és Alistair Sinclair , „  Approximating the permanent  ”, SIAM Journal on Computing , vol.  18, n o  6,1989, P.  1149–1178 ( ISSN  1095-7111 , DOI  10.1137 / 0218077 )
  7. Alistair Sinclair és Mark Jerrum „  Hozzávetőleges számítás, egységes termelési és gyorsan összekeverjük Markov-láncok  ” Információs és számítása , vol.  82, n o  1,1989, P.  93–133 ( DOI  10.1016 / 0890-5401 (89) 90067-9 )
  8. Joseph Halpern és Yoram Moses : „  Tudás és közismeret elosztott környezetben  ”, Journal of the ACM , vol.  37, n o  3,1990, P.  549–587 ( DOI  10.1145 / 79147.79161 )
  9. Seinosuke Toda , „A  PP ugyanolyan kemény, mint a polinom-idő hierarchia  ”, SIAM Journal on Computing , vol.  20, n o  5,1991, P.  865–877 ( DOI  10.1137 / 0220053 , online olvasás )
  10. Peter W. Shor , „  Polinomiális idő algoritmusai a primer faktoráláshoz és a diszkrét logaritmusok egy kvantum számítógépen  ”, SIAM Journal on Computing , vol.  26, n o  5,1997, P.  1484–1509 ( DOI  10.1137 / S0097539795293172 , online olvasás )
  11. Moshe Y. Vardi és Pierre Wolper , „  Reasoning about végtelen számítások  ”, Information and Computation , vol.  115, n o  1,1994, P.  1–37 ( DOI  10.1006 / inco.1994.1092 , online olvasás [ archívum2011. augusztus 25] )
  12. Uriel Feige , Shafi Goldwasser , Lovász László , Shmuel Safra és Mario Szegedy , „  Interaktív bizonyítások és a klikkek közelítésének keménysége  ”, Journal of the ACM , vol.  43, n o  21996, P.  268–292 ( DOI  10.1145 / 226643.226652 , online olvasás )
  13. Sanjeev Arora és Shmuel Safra , „  A bizonyítékok valószínűségi ellenőrzése: az NP új jellemzése  ”, Journal of the ACM , vol.  45, n o  1,1998, P.  70–122 ( DOI  10.1145 / 273865.273901 , online olvasás [ archívum2011. június 10] )
  14. Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan és Mario Szegedy , „A  bizonyítás igazolása és a közelítési problémák keménysége  ”, Journal of the ACM , vol.  45, n o  3,1998, P.  501–555 ( DOI  10.1145 / 278298.278306 , online olvasás [ archívum2011. június 10] )
  15. Géraud Sénizergues , „  L (A) = L (B)? a határozhatóság a teljes formális rendszerek eredménye  ”, Theor. Comput. Sci. , vol.  251 n o  12001, P.  1–166 ( DOI  10.1016 / S0304-3975 (00) 00285-1 )
  16. Y. Freund és RE Schapire , „  Az on-line tanulás döntéselméleti általánosítása és alkalmazás az ösztönzéshez  ”, Journal of Computer and System Sciences , vol.  55, n o  1,1997, P.  119–139 ( DOI  10.1006 / jcss.1997.1504 , online olvasás )
  17. Maurice Herlihy és Nir Shavit, „  Az aszinkron számítás topológiai szerkezete  ”, Journal of the ACM , vol.  46, n o  6,1999, P.  858–923 ( DOI  10.1145 / 331524.331529 , online olvasás )
  18. Michael Saks és Fotios Zaharoglou „  Wait-mentes k -set megállapodás lehetetlen: A topológia köztudomásúak  ” SIAM Journal on Computing , vol.  29, n o  5,2000, P.  1449–1483 ( DOI  10.1137 / S0097539796307698 )
  19. Noga Alon , Yossi Matias és Mario Szegedy , „  A frekvenciamomentumok közelítésének térbeli bonyolultsága  ”, Journal of Computer and System Sciences , vol.  58, n o  1,1999, P.  137–147 ( DOI  10.1006 / jcss.1995.1545 , online olvasás )
  20. Manindra Agrawal, Neeraj Kayal és Nitin Saxena, „  PRIMES is in P  ”, Annals of Mathematics , vol.  160, n o  22004, P.  781–793 ( DOI  10.4007 / annals.2004.160.781 , online olvasás [ archívum2011. június 7] )
  21. Alexander A. Razborov és Steven Rudich , "  Természetes bizonyítékok  ", Journal of Computer and System Sciences , vol.  55, n o  1,1997, P.  24–35 ( DOI  10.1006 / jcss.1997.1494 )
  22. Daniel A. Spielman és Shang-Hua Teng , „  Az algoritmusok simított elemzése: Miért tart a szimplex algoritmus általában polinomiális időt  ”, Journal of the ACM , vol.  51, n o  3,2004, P.  385-463 ( olvasható online [ archív2009. december 6] )
  23. Omer Reingold , Salil Vadhan és Avi Wigderson : „Az  entrópia hullámai, a cikk-cakk grafikon terméke és az új állandó fokú bővítők  ”, Annals of Mathematics , vol.  155, n o  1,2002, P.  157–187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Math Reviews  1888797 , olvassa el online [ archívum2009. december 7] )
  24. Omer Reingold , „  Irányítatlan kapcsolat a naplótérben  ”, Journal of the ACM , vol.  55, n o  4,2008, P.  1–24 ( online olvasás )
  25. Sanjeev Arora , „  Polinomiális idő-közelítő sémák az euklideszi utazó eladóhoz és egyéb geometriai problémák  ”, Journal of the ACM , vol.  45, n o  5,1998, P.  753–782 ( DOI  10.1145 / 290179.290180 )
  26. Joseph SB Mitchell , „  Guillotine Subdivisions Approximate Polygonal Subdivitions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems  ”, SIAM Journal on Computing , vol.  28, n o  4,1999, P.  1298–1309 ( ISSN  1095-7111 , DOI  10.1137 / S0097539796309764 )
  27. Johan Håstad , „  Néhány optimális megközelíthetlenségi eredmény  ”, Journal of the ACM , vol.  48,2001, P.  798–859 ( DOI  10.1145 / 502090.502098 , online olvasás )
  28. Elias Koutsoupias és Christos Papadimitriou , „A  legrosszabb eset egyensúlya  ”, Computer Science Review , vol.  3, n o  22009, P.  65–69 ( DOI  10.1016 / j.cosrev.2009.04.003 )
  29. Tim Roughgarden és Tardos Éva : „  Mennyire rossz az önző útválasztás?  ”, Journal of the ACM , vol.  49, n o  22002, P.  236–259 ( DOI  10.1145 / 506147.506153 )
  30. Noam Nisan és Amir Ronen , „  Algoritmikus mechanizmus tervezése  ”, Játékok és gazdasági magatartás , vol.  35, n csont  1-2,2001, P.  166–196 ( DOI  10.1006 / játék.1997.0790 )
  31. Dan Boneh és Matthew Franklin , „  Identitás alapú titkosítás a Weil párosításból  ”, SIAM Journal on Computing , vol.  32, n o  3,2003, P.  586–615 ( DOI  10.1137 / S0097539701398521 , Math Reviews  2001745 )
  32. Antoine Joux , „  Egyfordulós protokoll a háromoldalú Diffie-Hellman számára  ”, Journal of Cryptology , vol.  17, n o  4,2004, P.  263–276 ( DOI  10.1007 / s00145-004-0312-y , Math Reviews  2090557 )
  33. Ronald Fagin , Amnon Lotem és Moni Naor , „  Optimal aggregation algorithms for middleware  ”, Journal of Computer and System Sciences , vol.  66, n o  4,2003, P.  614-656 ( DOI  10.1016 / S0022-0000 (03) 00026-6 )
  34. Daniel A. Spielman és Shang-Hua Teng , „  Grafikonok spektrális eloszlása  ”, SIAM Journal on Computing , vol.  40, n o  4,2011, P.  981-1025 ( ISSN  0097-5397 , DOI  10.1137 / 08074489X ).
  35. Daniel A. Spielman és Shang-Hua Teng , „  Helyi fürtözési algoritmus a tömeges grafikonokhoz és alkalmazása majdnem lineáris időgrafikonok particionálására  ”, SIAM Journal on Computing , vol.  42, n o  1,2013, P.  1-26 ( ISSN  0097-5397 , DOI  10.1137 / 080744888 ).
  36. Daniel A. Spielman és Shang-Hua Teng , „  Szinte lineáris idő algoritmusok a szimmetrikus, átlósan domináns lineáris rendszerek előkondicionálásához és megoldásához  ”, SIAM Journal on Matrix Analysis and Applications , vol.  35, n o  3,2014, P.  835-885 ( ISSN  0895-4798 , DOI  10.1137 / 090771430 ).
  37. Peter W. O'Hearn, „  Források, párhuzamosság és helyi érvelés  ”, Theoretical Computer Science , vol.  375, n csont  1-3, 2007, P.  271-307.
  38. Stephen Brookes, „  A szemantika a párhuzamos elválasztási logikához  ”, Theoretical Computer Science , vol.  375, n csont  1-3, 2007, P.  227-270.
  39. Cynthia Dwork, Frank McSherry, Kobbi Nissim és Adam Smith, „  Zaj és érzékenység kalibrálása  ”, Private Data Analysis Journal of Privacy and Confidentiality , vol.  7, n o  3,2016.
  40. (in) Oded Regev , "  Mi rácsok, hibákkal tanulás, véletlenszerű lineáris kódok és rejtjelezés  " , Journal of the ACM , vol.  56, n o  6, 2009, P.  34: 1-34: 40 ( DOI  10.1145 / 1568318.1568324 ).
  41. (a) Irit Dinur , "  A PCP-tétel amplifikációval rés  " , Journal of the ACM , vol.  54, n o  3, 2007, P.  12.
  42. (in) Robin A. Moser és Tardos Gábor , "  konstruktív A Lovász Helyi Lemma általános bizonyítéka  " , Journal of the ACM , vol.  57, n o  2 2010, P.  11: 1–11: 15
  43. Andrei A. Bulatov, „  A számlálási kényszer elégedettségi problémájának összetettsége  ”, Journal of the ACM , Association for Computing Machinery (ACM), vol.  60, n o  5,2013, P.  1–41 ( ISSN  0004-5411 , DOI  10.1145 / 2528400 )
  44. Martin Dyer és David Richerby , „  Hatékony kettéosztás a számolási kényszer-elégedettség problémájához  ”, Society for Industrial & Applied Mathematics (SIAM) , vol.  42, n o  3, 2013, P.  1245–1274 ( ISSN  0097-5397 , DOI  10.1137 / 100811258 )
  45. Jin-Yi Cai és Xi Chen, „  A CSP számlálásának komplexitása összetett súlyokkal  ”, Association for Computing Machinery (ACM) , vol.  64, n o  3, 2017. június 22, P.  1–39 ( ISSN  0004-5411 , DOI  10.1145 / 2822891 )

Megjegyzések

Megjegyzések

  1. Az első bekezdései
  2. Jacques Stern , "  Antoine Joux, Prix Gödel 2013  ", 1024 - Bulletin az informatikai társadalom Franciaország , n o  1,2013 szeptember, P.  107–110 ( online olvasás )
  3. Az EATCS honlapján: A díjat Kurt Gödel tiszteletére nevezik ki a matematikai logikához való jelentős hozzájárulásának és érdeklődésének elismeréseként, amelyet nem sokkal Neumann halála előtt John von Neumannnak írt levelében fedeztek fel, amely a híressé vált " P versus NP "kérdés.
  4. A 2014. évi Godel-díj hivatalos bejelentése .
  5. Cikk a cikkről és a díjról: Thore Husfeldt, „  Személyes valóság (Gödel-díj 2014)  ” [ archív du2015. május 4] ,2014(megtekintve 2015. április 30-án ) .
  6. "  2015-ös Gödel-díj  " , a SIGACT- on
  7. "  2016 Gödel-díj  " , az EATCS- on
  8. "  2017 Gödel-díj  " , az EATCS- on .
  9. "  2021-es Gödel-díj idézet  "
(fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „  Gödel-díj  ” ( lásd a szerzők listáját ) .

Lásd is

Kapcsolódó cikk

Külső linkek