Gödelova cena - Gödel Prize

The Gödelova cena je výroční cena za vynikající práce v oblasti teoretická informatika, dané společně Evropská asociace pro teoretickou informatiku (EATCS) a Sdružení pro výpočetní techniku Zvláštní zájmová skupina pro algoritmy a výpočetní teorii (ACM SIGACT ). Cena je pojmenována na počest Kurt Gödel. Gödelův vztah k teoretické informatice spočívá v tom, že jako první zmínil „P versus NP "otázka, v dopise z roku 1956 John von Neumann ve kterém se Gödel zeptal, zda jistý NP-kompletní problém lze vyřešit v kvadratickém nebo lineárním čase.[1]

Gödelova cena se uděluje od roku 1993. Cena se uděluje buď na STOC (ACM Symposium on Theory of Computing, jeden z hlavních severní Amerika konference v teoretické informatice) nebo ICALP (Mezinárodní kolokvium o automatech, jazycích a programování, jeden z hlavních evropský konference v oboru). Aby měl nárok na cenu, musí být v posledních 14 (dříve 7) letech publikován článek v časopise, který byl posouzen. Cena zahrnuje odměnu 5 000 USD.[2]

Vítěze Ceny vybírá šestičlenná komise. Předseda EATCS a předseda SIGACT jmenují do výboru tři členy, kteří mají zastávat střídaná tříletá období. Výboru střídavě předsedají zástupci EATCS a SIGACT.

Příjemci

RokJménaPoznámkyRok vydání
1993László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, a Charles Rackoffpro rozvoj interaktivní kontrolní systémy1988,[papír 1] 1989[papír 2]
1994Johan Håstadpro exponenciální dolní mez na velikost konstantní hloubka Booleovské obvody (pro paritní funkce ).1989[papír 3]
1995Neil Immerman a Róbert Szelepcsényipro Immerman – Szelepcsényiho věta pokud jde o nedeterministickou složitost prostoru1988,[papír 4] 1988[papír 5]
1996Mark Jerrum a Alistair Sinclairpro práci na Markovovy řetězy a přiblížení permanent matice1989,[papír 6] 1989[papír 7]
1997Joseph Halpern a Yoram Mojžíšpro definování formální představy o „znalostech“ v distribuovaných prostředích1990[papír 8]
1998Seinosuke Todapro Todova věta který ukázal souvislost mezi řešeními počítání (PP ) a střídání kvantifikátorů (PH )1991[papír 9]
1999Peter Shorpro Shorův algoritmus pro factoring čísla v polynomiální čas na kvantový počítač1997[papír 10]
2000Moshe Y. Vardi a Pierre Wolperpro práci na časová logika s konečné automaty1994[papír 11]
2001Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Súdán, a Mario Szegedypro Věta o PCP a její aplikace na tvrdost aproximace1996,[papír 12] 1998,[papír 13] 1998[papír 14]
2002Géraud Sénizerguesza prokázání rovnocennosti deterministické posunovací automaty je rozhodnutelné2001[papír 15]
2003Yoav Freund a Robert Schapirepro AdaBoost algoritmus v strojové učení1997[papír 16]
2004Maurice Herlihy, Michael Saks, Nir Shavit a Fotios Zaharogloupro aplikace topologie k teorii distribuované výpočty1999,[papír 17] 2000[papír 18]
2005Noga Alon, Yossi Matias a Mario Szegedyza jejich základní příspěvek do streamovací algoritmy1999[papír 19]
2006Manindra Agrawal, Neeraj Kayal, Nitin Saxenapro Test prvosti AKS2004[papír 20]
2007Alexander Razborov, Steven Rudichpro přírodní důkazy1997[papír 21]
2008Daniel Spielman, Shanghua Tengpro uhlazená analýza algoritmů2004[papír 22]
2009Omer Reingold, Salil Vadhan, Avi Wigdersonpro cik-cak produkt z grafy a neorientovaná konektivita v prostor protokolu2002,[papír 23] 2008[papír 24]
2010Sanjeev Arora, Joseph S. B. Mitchellza jejich současný objev a schéma aproximace v polynomiálním čase (PTAS) pro euklidovce Problém obchodního cestujícího (ETSP)1998,[papír 25]

1999[papír 26]

2011Johan Håstadpro prokázání optimálních výsledků nepřístupnosti pro různé kombinatorické problémy2001[papír 27]
2012Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen [de ], Tim Roughgarden a Éva Tardospro položení základů teorie algoritmických her[3]2009,[papír 28] 2002,[papír 29] 2001[papír 30]
2013Dan Boneh, Matthew K. Franklin, a Antoine Jouxpro multi-party Výměna klíčů Diffie – Hellman a Schéma Boneh – Franklin v kryptografii[4]2003,[papír 31]

2004[papír 32]

2014Ronald Fagin, Amnon Lotem [fr ], a Moni Naorpro optimální agregační algoritmy pro middleware[5]2003,[papír 33]
2015Daniel Spielman, Shanghua Tengza jejich sérii článků o řečnících Laplacian v téměř lineárním čase[6]

2011[papír 34]2013[papír 35]2014[papír 36]

2016Stephen Brookes a Peter W. O'Hearnza jejich vynález Logika souběžné separace2007,[papír 37] 2007[papír 38]
2017[2]Cynthia Dwork, Frank McSherry, Kobbi Nissim, a Adam D. Smithpro vynález rozdílné soukromí2006[papír 39]
2018[7]Oded Regevza zavedení učení s chybami problém2009[papír 40]
2019[8]Irit Dinurza její nový důkaz Věta o PCP zesílením mezery2007[papír 41]
2020[9]Robin Moser a Gábor Tardospro jejich konstruktivní důkaz z Lovász místní lemma2010[papír 42]

Vítězné papíry

  1. ^ Babai, László; Moran, Shlomo (1988), „Hry Arthur-Merlin: randomizovaný kontrolní systém a hierarchie třídy složitosti“ (PDF), Journal of Computer and System Sciences, 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN  0022-0000
  2. ^ Goldwasser, S .; Micali, S .; Rackoff, C. (1989), „Znalostní složitost interaktivních důkazních systémů“ (PDF), SIAM Journal on Computing, 18 (1): 186–208, CiteSeerX  10.1.1.397.4002, doi:10.1137/0218012, ISSN  1095-7111
  3. ^ Håstad, Johan (1989), „Téměř optimální spodní hranice pro obvody s malou hloubkou“ (PDF), v Micali, Silvio (ed.), Náhodnost a výpočetPokroky ve výzkumu výpočetní techniky, 5, JAI Press, str. 6–20, ISBN  978-0-89232-896-3, archivovány z originál (PDF) dne 2012-02-22
  4. ^ Immerman, Neil (1988), „Nedeterministický prostor je uzavřen doplňováním“ (PDF), SIAM Journal on Computing, 17 (5): 935–938, CiteSeerX  10.1.1.54.5941, doi:10.1137/0217058, ISSN  1095-7111
  5. ^ Szelepcsényi, R. (1988), "Metoda vynuceného výčtu nedeterministických automatů" (PDF), Acta Informatica, 26 (3): 279–284, doi:10.1007 / BF00299636, hdl:10338.dmlcz / 120489
  6. ^ Sinclair, A .; Jerrum, M. (1989), "Přibližné počítání, generování uniform a rychlé míchání Markovových řetězců", Informace a výpočet, 82 (1): 93–133, doi:10.1016/0890-5401(89)90067-9, ISSN  0890-5401
  7. ^ Jerrum, M .; Sinclair, Alistair (1989), „Aproximace stálého“, SIAM Journal on Computing, 18 (6): 1149–1178, CiteSeerX  10.1.1.431.4190, doi:10.1137/0218077, ISSN  1095-7111
  8. ^ Halpern, Joseph; Mojžíš, Yorame (1990), „Znalosti a obecné znalosti v distribuovaném prostředí“ (PDF), Deník ACM, 37 (3): 549–587, arXiv:cs / 0006009, doi:10.1145/79147.79161
  9. ^ Toda, Seinosuke (1991), „PP je stejně tvrdý jako hierarchie polynomiálního času“ (PDF), SIAM Journal on Computing, 20 (5): 865–877, CiteSeerX  10.1.1.121.1246, doi:10.1137/0220053, ISSN  1095-7111
  10. ^ Shor, Peter W. (1997), „Algoritmy polynomiálního času pro Prime Factorization a diskrétní logaritmy na kvantovém počítači“ (PDF), SIAM Journal on Computing, 26 (5): 1484–1509, arXiv:quant-ph / 9508027, doi:10.1137 / S0097539795293172, ISSN  1095-7111[trvalý mrtvý odkaz ]
  11. ^ Vardi, Moshe Y .; Wolper, Pierre (1994), „Důvod k nekonečným výpočtům“ (PDF), Informace a výpočet, 115 (1): 1–37, doi:10.1006 / inco.1994.1092, ISSN  0890-5401, archivovány z originál (PDF) dne 25. 8. 2011
  12. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), „Interaktivní důkazy a tvrdost přibližných klik“ (PDF), Deník ACM, 43 (2): 268–292, doi:10.1145/226643.226652, ISSN  0004-5411
  13. ^ Arora, Sanjeev; Safra, Shmuel (1998), „Pravděpodobnostní kontrola důkazů: nová charakteristika NP“ (PDF), Deník ACM, 45 (1): 70–122, doi:10.1145/273865.273901, ISSN  0004-5411, archivovány z originál (PDF) dne 10.06.2011
  14. ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Súdán, Madhu; Szegedy, Mario (1998), „Ověření důkazu a tvrdost problémů s aproximací“ (PDF), Deník ACM, 45 (3): 501–555, CiteSeerX  10.1.1.145.4652, doi:10.1145/278298.278306, ISSN  0004-5411, archivovány z originál (PDF) dne 10.06.2011
  15. ^ Sénizergues, Géraud (2001), „L (A) = L (B)? Rozhodnutelnost vyplývá z úplných formálních systémů“, Teor. Comput. Sci., 251 (1): 1–166, doi:10.1016 / S0304-3975 (00) 00285-1, ISSN  0304-3975
  16. ^ Freund, Y .; Schapire, R.E. (1997), „Rozhodnutí-teoretické zobecnění on-line učení a aplikace na podporu“ (PDF), Journal of Computer and System Sciences, 55 (1): 119–139, doi:10.1006 / jcss.1997.1504, ISSN  1090-2724
  17. ^ Herlihy, Maurice; Shavit, Nir (1999), "Topologická struktura asynchronní vypočítatelnosti" (PDF), Deník ACM, 46 (6): 858–923, CiteSeerX  10.1.1.78.1455, doi:10.1145/331524.331529. Přednáška o ceně Gödel
  18. ^ Saks, Michael; Zaharoglou, Fotios (2000), „Wait-free k-souprava není možná: topologie veřejného poznání ", SIAM Journal on Computing, 29 (5): 1449–1483, doi:10.1137 / S0097539796307698
  19. ^ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), „Prostorová složitost aproximace frekvenčních momentů“ (PDF), Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006 / jcss.1997.1545. Poprvé představeno na Symposium on Theory of Computing (STOC) v roce 1996.
  20. ^ Agrawal, M .; Kayal, N .; Saxena, N. (2004), „PRIMES je v P“ (PDF), Annals of Mathematics, 160 (2): 781–793, doi:10.4007 / annals.2004.160.781, ISSN  0003-486X, archivovány z originál (PDF) dne 07.06.2011
  21. ^ Razborov, Alexander A .; Rudich, Steven (1997), „Přírodní důkazy“, Journal of Computer and System Sciences, 55 (1): 24–35, doi:10.1006 / jcss.1997.1494, ISSN  0022-0000, ECCC  TR94-010
  22. ^ Spielman, Daniel A .; Teng, Shang-Hua (2004), „Vyhlazená analýza algoritmů: Proč simplexní algoritmus obvykle trvá polynomiální čas“ (PDF), J. ACM, 51 (3): 385–463, arXiv:matematika / 0212413, doi:10.1145/990308.990310, ISSN  0004-5411[trvalý mrtvý odkaz ]
  23. ^ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), „Entropické vlny, produkt klikatého grafu a nové expandéry konstantního stupně“ (PDF), Annals of Mathematics, 155 (1): 157–187, CiteSeerX  10.1.1.236.8669, doi:10.2307/3062153, ISSN  0003-486X, JSTOR  3062153, PAN  1888797[trvalý mrtvý odkaz ]
  24. ^ Reingold, Omer (2008), „Neusměrněné připojení v logovém prostoru“, J. ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN  0004-5411[trvalý mrtvý odkaz ]
  25. ^ Arora, Sanjeev (1998), „Schémata polynomiálního přibližování času pro euklidovského obchodního cestujícího a další geometrické problémy“, Deník ACM, 45 (5): 753–782, CiteSeerX  10.1.1.23.6765, doi:10.1145/290179.290180, ISSN  0004-5411
  26. ^ Mitchell, Joseph S. B. (1999), „Guillotine Subdivisions Aproximate Polygonal Subdivisions: A Simple Polynomial-Time Aproximation Scheme for Geometric TSP, k-MST, and Related Problems“, SIAM Journal on Computing, 28 (4): 1298–1309, doi:10.1137 / S0097539796309764, ISSN  1095-7111
  27. ^ Håstad, Johan (2001), „Některé optimální výsledky nepřibližnosti“ (PDF), Deník ACM, 48 (4): 798–859, CiteSeerX  10.1.1.638.2808, doi:10.1145/502090.502098, ISSN  0004-5411
  28. ^ Koutsoupias, Elias; Papadimitriou, Christos (2009). „Nejhorší rovnováha“. Recenze informatiky. 3 (2): 65–69. doi:10.1016 / j.cosrev.2009.04.003.
  29. ^ Roughgarden, Tim; Tardos, Éva (2002). „Jak špatné je sobecké směrování?“. Deník ACM. 49 (2): 236–259. CiteSeerX  10.1.1.147.1081. doi:10.1145/506147.506153.
  30. ^ Nisan, Noam; Ronen, Amir (2001). "Návrh algoritmického mechanismu". Hry a ekonomické chování. 35 (1–2): 166–196. CiteSeerX  10.1.1.21.1731. doi:10.1006 / hra.1999.0790.
  31. ^ Boneh, Dan; Franklin, Matthew (2003). "Šifrování založené na identitě z Weilova párování". SIAM Journal on Computing. 32 (3): 586–615. CiteSeerX  10.1.1.66.1131. doi:10.1137 / S0097539701398521. PAN  2001745.
  32. ^ Joux, Antoine (2004). „Jednokruhový protokol pro trojstranný Diffie-Hellman“. Journal of Cryptology. 17 (4): 263–276. doi:10.1007 / s00145-004-0312-r. PAN  2090557.
  33. ^ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). Msgstr "Optimální agregační algoritmy pro middleware". Journal of Computer and System Sciences. 66 (4): 614–656. arXiv:cs / 0204046. doi:10.1016 / S0022-0000 (03) 00026-6.
  34. ^ Spielman, Daniel A .; Teng, Shang-Hua (2011). "Spektrální sparifikace grafů". SIAM Journal on Computing. 40 (4): 981–1025. arXiv:0808.4134. doi:10.1137 / 08074489X. ISSN  0097-5397.
  35. ^ Spielman, Daniel A .; Teng, Shang-Hua (2013). "Místní klastrovací algoritmus pro masivní grafy a jeho aplikace pro téměř lineární dělení časových grafů". SIAM Journal on Computing. 42 (1): 1–26. arXiv:0809.3232. doi:10.1137/080744888. ISSN  0097-5397.
  36. ^ Spielman, Daniel A .; Teng, Shang-Hua (2014). "Téměř lineární časové algoritmy pro předběžné úpravy a řešení symetrických, úhlopříčně dominujících lineárních systémů". SIAM Journal on Matrix Analysis and Applications. 35 (3): 835–885. arXiv:cs / 0607105. doi:10.1137/090771430. ISSN  0895-4798.
  37. ^ Brookes, Stephen (2007). „Sémantika pro logiku souběžné separace“ (PDF). Teoretická informatika. 375 (1–3): 227–270. doi:10.1016 / j.tcs.2006.12.034.
  38. ^ O'Hearn, Peter (2007). „Zdroje, souběžnost a místní uvažování“ (PDF). Teoretická informatika. 375 (1–3): 271–307. doi:10.1016 / j.tcs.2006.12.035.
  39. ^ Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (eds.). Kalibrace šumu na citlivost při analýze soukromých dat. Teorie kryptografie (TCC). Přednášky z informatiky. 3876. Springer-Verlag. 265–284. doi:10.1007/11681878_14. ISBN  978-3-540-32731-8.
  40. ^ Regev, Oded (2009). "Na mřížkách, učení s chybami, náhodné lineární kódy a kryptografie". Deník ACM. 56 (6): 1–40. CiteSeerX  10.1.1.215.3543. doi:10.1145/1568318.1568324.
  41. ^ Dinur, Irit (2007). „Věta o PCP zesílením mezery“. Deník ACM. 54 (3): 12 – es. doi:10.1145/1236457.1236459.
  42. ^ "Konstruktivní důkaz obecné Lovász Local Lemma". Deník ACM. 57 (2). 2010. doi:10.1145/1667053. ISSN  0004-5411.

Viz také

Poznámky

  1. ^ „Gödelův dopis“. 2009-02-12.
  2. ^ A b „Cena Gödel za rok 2017“. Evropská asociace pro teoretickou informatiku. EATCS. Citováno 29. března 2017.
  3. ^ „Tři články citované pro položení základů růstu v algoritmické teorii her“. 16. května 2012. Archivovány od originál dne 18. července 2013. Citováno 16. května 2012.
  4. ^ Skupina ACM představuje Gödelovu cenu za pokrok v kryptografii: Tři počítačoví vědci citovaní pro inovace, které zlepšují zabezpečení Archivováno 01.06.2013 na Wayback Machine, Sdružení pro výpočetní techniku, 29. května 2013.
  5. ^ Příjemci dosáhli převratných výsledků agregace dat z více zdrojů, Sdružení pro výpočetní techniku, 30. dubna 2014.
  6. ^ Vyhlášení ceny Gödel za rok 2015 Archivováno 09.12.2017 na Wayback Machine podle Sdružení pro výpočetní techniku.
  7. ^ „Citace Gödelovy ceny za rok 2018“.
  8. ^ „Citace Gödelovy ceny 2019“.
  9. ^ „Citace Gödelovy ceny 2020“.

Reference