Gödel -Preis

Nicht zu verwechseln mit Gödel Lecture.

Das Gödel -Preis ist ein jährlicher Preis für herausragende Papiere im Bereich von Theoretische Informatikgemeinsam von der gegeben durch die Europäische Vereinigung für theoretische Informatik (Eatcs) und die Verband für Rechenmaschinen Spezialinteressengruppe für Algorithmen und Computertheorie (Rechentheorie (ACM Sigact). Die Auszeichnung ist zu Ehren von von genannt Kurt Gödel. Gödels Verbindung zur theoretischen Informatik ist, dass er der erste war, der das erwähnte "P gegen NP"Frage in einem Brief von 1956 an John von Neumann in dem Gödel fragte, ob eine bestimmte NP-Complete Problem könnte gelöst werden quadratisch oder lineare Zeit.[1]

Der Gödel -Preis wird seit 1993 verliehen. Der Preis wird entweder bei STOC (ACM Symposium über die Computertheorie, einer der wichtigsten nordamerikanisch Konferenzen in theoretischer Informatik) oder ICICP (Internationales Kolloquium über Automaten, Sprachen und Programmierung, einer der wichtigsten europäisch Konferenzen im Feld). Um für den Preis berechtigt zu sein, muss ein Papier innerhalb der letzten 14 (ehemals 7) Jahre in einem Schiedsrichterjournal veröffentlicht werden. Der Preis beinhaltet eine Belohnung von 5000 US -Dollar.[2]

Der Gewinner des Preises wird von einem Ausschuss von sechs Mitgliedern ausgewählt. Der EATCS-Präsident und der Sigact-Vorsitzende ernennen jeweils drei Mitglieder in das Komitee, um gestaffeltes Dreijahresverband zu dienen. Das Komitee wird abwechselnd von Vertretern von EatCs und Sigact geleitet.

Empfänger

Jahr Name (en) Anmerkungen Veröffentlichungsjahr
1993 László Babai, SHAFI GOLDSER, Silvio Micali, Shlomo Moran, und Charles Rackoff für die Entwicklung von Interaktive Proof -Systeme 1988,[Papier 1] 1989[Papier 2]
1994 Johan Håstad für eine Exponential Untergrenze an die Größe von konstant tiefe Boolesche Schaltungen (für die Paritätsfunktion). 1989[Papier 3]
1995 Neil Immerman und Róbert Szelepcsényi für die Imerman -Szelepcsényi Theorem In Bezug auf nicht deterministische Raumkomplexität 1988,[Papier 4] 1988[Papier 5]
1996 Mark Jerrum und Alistair Sinclair for work on Markov -Ketten und die Annäherung der dauerhaft einer Matrix 1989,[Papier 6] 1989[Papier 7]
1997 Joseph Halpern und Yoram Moses für die Definition eines formalen Begriffs von "Wissen" in verteilten Umgebungen 1990[Papier 8]
1998 Seinosuke Toda zum Todas Satz die einen Zusammenhang zwischen Zähllösungen zeigten (Pp) und Wechsel von Quantifizierern (PH) 1991[Papier 9]
1999 Peter Shor zum Shors Algorithmus zum Factoring Zahlen in Polynomzeit auf einen Quantencomputer 1997[Papier 10]
2000 Moshe Y. Vardi und Pierre Wolper for work on zeitliche Logik mit Finite Automaten 1994[Papier 11]
2001 Sanjeev Arora, Uriel Feige, SHAFI GOLDSER, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, und Mario Szegedy für die PCP -Theorem und seine Anwendungen für die Annäherungshärte 1996,[Papier 12] 1998,[Papier 13] 1998[Papier 14]
2002 Géraud Sénizergues für den Beweis dieser Äquivalenz von Deterministische Pushdown -Automaten ist entschlossen 2001[Papier 15]
2003 Yoav Freund und Robert Schapire für die Adaboost Algorithmus in maschinelles Lernen 1997[Papier 16]
2004 Maurice Herlihy, Michael Saks, Nir Shavit und Fotios zaharoglou für Anwendungen von Topologie zur Theorie von verteiltes Computer 1999,[Papier 17] 2000[Papier 18]
2005 Noga Alon, Yossi Matias und Mario Szegedy für ihren grundlegenden Beitrag zu Streaming -Algorithmen 1999[Papier 19]
2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena für die ASS -Primalitätstest 2004[Papier 20]
2007 Alexander Razborov, Steven Rudich zum Natürliche Beweise 1997[Papier 21]
2008 Daniel Spielman, Shang-Hua Teng zum Geglättete Analyse von Algorithmen 2004[Papier 22]
2009 Omer Reingold, Salil Vadhan, Avi Wigderson zum Zick-Zack-Produkt von Grafiken und ungerichtete Konnektivität in Protokollraum 2002,[Papier 23] 2008[Papier 24]
2010 Sanjeev Arora, Joseph S. B. Mitchell für ihre gleichzeitige Entdeckung von a Polynom-Zeit-Approximationsschema (PTAs) für den Euklidaner Problem mit reisenden Verkäufern (ETSP) 1998,[Papier 25]

1999[Papier 26]

2011 Johan Håstad Für die Nachweis optimaler Unangemessenheitsergebnisse für verschiedene kombinatorische Probleme 2001[Papier 27]
2012 Elias Koutsupias, Christos Papadimitriou, Noam NisanAmir Ronen[DE], Tim Roughgarden und Éva Tardos zum Festlegen der Grundlagen von Algorithmische Spieltheorie[3] 2009,[Papier 28] 2002,[Papier 29] 2001[Papier 30]
2013 Dan Boneh, Matthew K. Franklin, und Antoine Joux für Multi-Party Diffie -Hellman Key Exchange und die Boneh -Franklin -Schema in der Kryptographie[4] 2003,[Papier 31]

2004[Papier 32]

2014 Ronald Fagin, Amnon Lotem[FR], und Moni Naor Für optimale Aggregationsalgorithmen für Middleware[5] 2003,[Papier 33]
2015 Daniel Spielman, Shang-Hua Teng für ihre Reihe von Papieren zu fast linearer Laplace-Solvers[6]

2011[Papier 34] 2013[Papier 35] 2014[Papier 36]

2016 Stephen Brookes und Peter W. O'hearn für ihre Erfindung von Gleichzeitige Trennungslogik 2007,[Papier 37] 2007[Papier 38]
2017[2] Cynthia Dwork, Frank McSerry, Kobbi Nissim, und Adam D. Smith zur Erfindung von Differentielle Privatsphäre 2006[Papier 39]
2018[7] ODED Regev zur Einführung der Lernen mit Fehlern Problem 2009[Papier 40]
2019[8] IRIT DINUR für ihren neuen Beweis der PCP -Theorem durch Lückenverstärkung 2007[Papier 41]
2020[9] Robin Moser und Gábor Tardos für ihre konstruktiver Beweis des Lovász Lokale Lemma 2010[Papier 42]
2021[10] Andrei Bulatov, Jin-yi Cai, Xi Chen, Martin Dyerund David Richerby für ihre Arbeit an der Klassifizierung der Komplexität zählen von Probleme mit der Einschränkung der Zufriedenheit 2013[Papier 43]

2013[Papier 44] 2017[Papier 45]

2022[11] Zvika Brakerski, Craig Gentryund Vinod Vaikuntanathan Für ihre transformativen Beiträge zur Kryptographie, indem sie effizient effizient konstruieren Homomorphe Verschlüsselung (Fhe) Schemata 2014,[Papier 46] 2014[Papier 47]

Gewinnpapiere

  1. ^ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin-Spiele: Ein randomisiertes Proof-System und eine Hierarchie der Komplexitätsklasse" (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), "Die Wissenskomplexität interaktiver Beweissysteme" (PDF), Siam Journal über Computing, 18 (1): 186–208, Citeseerx 10.1.1.397.4002, doi:10.1137/0218012, ISSN 1095-7111
  3. ^ Håstad, Johan (1989), "Fast optimale Untergrenzen für kleine Tiefenschaltungen" (PDF)in Micali, Silvio (Hrsg.), Zufälligkeit und Berechnung, Fortschritte in der Computerforschung, Vol. 5, Jai Press, S. 6–20, ISBN 978-0-89232-896-3, archiviert von das Original (PDF) am 2012-02-22
  4. ^ Immerman, Neil (1988),, "Nichtdeterministischer Raum ist unter Komplementation geschlossen" (PDF), Siam Journal über Computing, 17 (5): 935–938, Citeseerx 10.1.1.54.5941, doi:10.1137/0217058, ISSN 1095-7111
  5. ^ Szelepcsényi, R. (1988), "Die Methode der erzwungenen Aufzählung für nicht deterministische Automaten" (PDF), Acta Informatica, 26 (3): 279–284, doi:10.1007/bf00299636, HDL:10338.DMLCZ/120489, S2CID 10838178
  6. ^ Sinclair, A.; Jerrum, M. (1989), "ungefähre Zählung, einheitliche Erzeugung und rasante Mischung von Markov -Ketten", Informationen und Berechnung, 82 (1): 93–133, doi:10.1016/0890-5401 (89) 90067-9, ISSN 0890-5401
  7. ^ Jerrum, M.; Sinclair, Alistair (1989), "ungefähr den Ständigen", Siam Journal über Computing, 18 (6): 1149–1178, Citeseerx 10.1.1.431.4190, doi:10.1137/0218077, ISSN 1095-7111
  8. ^ Halpern, Joseph; Moses, Yoram (1990), "Wissen und allgemeines Wissen in einer verteilten Umgebung" (PDF), Journal of the ACM, 37 (3): 549–587, Arxiv:CS/0006009, doi:10.1145/79147.79161, S2CID 52151232
  9. ^ Toda, Seinosuke (1991), "PP ist so schwer wie die Polynom-Zeit-Hierarchie" (PDF), Siam Journal über Computing, 20 (5): 865–877, Citeseerx 10.1.1.121.1246, doi:10.1137/0220053, ISSN 1095-7111
  10. ^ Shor, Peter W. (1997), "Polynomzeitalgorithmen für Primfaktorisierung und diskrete Logarithmen auf einem Quantencomputer", Siam Journal über Computing, 26 (5): 1484–1509, Arxiv:Quant-Ph/9508027, doi:10.1137/s0097539795293172, ISSN 1095-7111, S2CID 2337707
  11. ^ Vardi, Moshe Y.; Wolper, Pierre (1994), "Argumentation über unendliche Berechnungen" (PDF), Informationen und Berechnung, 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, archiviert von das Original (PDF) Am 2011-08-25
  12. ^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Interaktive Beweise und die Härte der Annäherung von Cliquen" (PDF), Journal of the ACM, 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411
  13. ^ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistische Überprüfung von Beweisen: Eine neue Charakterisierung von NP" (PDF), Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, S2CID 751563, archiviert von das Original (PDF) Am 2011-06-10
  14. ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Beweisüberprüfung und die Härte von Annäherungsproblemen" (PDF), Journal of the ACM, 45 (3): 501–555, Citeseerx 10.1.1.145.4652, doi:10.1145/278298.278306, ISSN 0004-5411, S2CID 8561542, archiviert von das Original (PDF) Am 2011-06-10
  15. ^ Sénizergues, Géraud (2001), "L (a) = l (b) - Dekidabilitätsergebnisse aus vollständigen formalen Systemen", Theor. Computer. Sci., 251 (1): 1–166, doi:10.1016/s0304-3975 (00) 00285-1, ISSN 0304-3975
  16. ^ Freund, Y.; Schapire, R.E. (1997),, "Eine entscheidende theoretische Verallgemeinerung des Online-Lernens und eine Anwendung auf die Steigerung" (PDF), Journal of Computer and System Sciences, 55 (1): 119–139, doi:10.1006/jcs.1997.1504, ISSN 1090-2724
  17. ^ Herlihy, Maurice; Shavit, Nir (1999), "Die topologische Struktur der asynchronen Berechnbarkeit" (PDF), Journal of the ACM, 46 (6): 858–923, Citeseerx 10.1.1.78.1455, doi:10.1145/331524.331529, S2CID 5797174. Götel -Preisvorlesung
  18. ^ Saks, Michael; Zaharoglou, Fotios (2000), "wartungsfrei k-Set -Vereinbarung ist unmöglich: Die Topologie des öffentlichen Wissens ", Siam Journal über Computing, 29 (5): 1449–1483, doi:10.1137/s0097539796307698
  19. ^ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "Die Raumkomplexität der Annäherung der Frequenzmomente" (PDF), Journal of Computer and System Sciences, 58 (1): 137–147, doi:10.1006/jcs.1997.1545. Zuerst präsentiert am Symposium über die Computertheorie (STOC) 1996.
  20. ^ Agrawal, M.; Kayal, N.; Saxena, N. (2004), "Primes is in P", Annalen der Mathematik, 160 (2): 781–793, doi:10.4007/Annals.2004.160.781, ISSN 0003-486X
  21. ^ Razborov, Alexander A.; Rudich, Steven (1997), "Natural Proofs", Journal of Computer and System Sciences, 55 (1): 24–35, doi:10.1006/jcs.1997.1494, ISSN 0022-0000, ECCC TR94-010
  22. ^ Spielman, Daniel A.; Teng, Shang-Hua (2004), "Geglättete Analyse von Algorithmen: Warum der Simplex -Algorithmus normalerweise Polynomzeit braucht", J. ACM, 51 (3): 385–463, Arxiv:Math/0212413, doi:10.1145/990308.990310, ISSN 0004-5411
  23. ^ Reingold, Omer; Vadhan, Salil; Wigderson, Avi (2002), "Entropy Waves, das Zick-Zack-Graph-Produkt und neue Expositionen mit konstantem Grad", Annalen der Mathematik, 155 (1): 157–187, Citeseerx 10.1.1.236.8669, doi:10.2307/3062153, ISSN 0003-486X, JStor 3062153, HERR 1888797, S2CID 120739405
  24. ^ Reingold, Omer (2008), "Unbekannte Konnektivität im Protokollraum", J. ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411, S2CID 207168478[Permanent Dead Link]
  25. ^ Arora, Sanjeev (1998), "Polynomzeitnäherungsschemata für euklidische Reiseverkäufer und andere geometrische Probleme", Journal of the ACM, 45 (5): 753–782, Citeseerx 10.1.1.23.6765, doi:10.1145/290179.290180, ISSN 0004-5411, S2CID 3023351
  26. ^ Mitchell, Joseph S. B. (1999), "Guillotine-Unterteilungen ungefähre polygonale Unterteilungen: Ein einfaches Polynom-Zeit-Approximationsschema für geometrische TSP, K-MST und verwandte Probleme", Siam Journal über Computing, 28 (4): 1298–1309, doi:10.1137/s0097539796309764, ISSN 1095-7111
  27. ^ Håstad, Johan (2001), "Einige optimale Unangemessenheitsergebnisse" (PDF), Journal of the ACM, 48 (4): 798–859, Citeseerx 10.1.1.638.2808, doi:10.1145/502090.502098, ISSN 0004-5411, S2CID 5120748
  28. ^ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-Case-Gleichgewichte". Informatikbewertung. 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
  29. ^ Roughgarden, Tim; Tardos, Éva (2002). "Wie schlimm ist egoistisches Routing?". Journal of the ACM. 49 (2): 236–259. Citeseerx 10.1.1.147.1081. doi:10.1145/506147.506153. S2CID 207638789.
  30. ^ Nisan, Noam; Ronen, Amir (2001). "Algorithmischer Mechanismus -Design". Spiele und wirtschaftliches Verhalten. 35 (1–2): 166–196. Citeseerx 10.1.1.21.1731. doi:10.1006/game.1999.0790.
  31. ^ Boneh, Dan; Franklin, Matthew (2003). "Identitätsbasierte Verschlüsselung aus der Weilpaarung". Siam Journal über Computing. 32 (3): 586–615. Citeseerx 10.1.1.66.1131. doi:10.1137/s0097539701398521. HERR 2001745.
  32. ^ Joux, Antoine (2004). "Ein rundes Protokoll für dreigliedrige Diffie-Hellman". Journal of Cryptology. 17 (4): 263–276. doi:10.1007/s00145-004-0312-y. HERR 2090557. S2CID 3350730.
  33. ^ Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Optimale Aggregationsalgorithmen für 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). "Spektrale Sparsifikation von Graphen". Siam Journal über Computing. 40 (4): 981–1025. Arxiv:0808.4134. doi:10.1137/08074489X. ISSN 0097-5397. S2CID 9646279.
  35. ^ Spielman, Daniel A.; Teng, Shang-Hua (2013). "Ein lokaler Clustering -Algorithmus für massive Graphen und seine Anwendung auf nahezu lineare Zeitgraphen -Partitionierung". Siam Journal über Computing. 42 (1): 1–26. Arxiv:0809.3232. doi:10.1137/080744888. ISSN 0097-5397. S2CID 9151077.
  36. ^ Spielman, Daniel A.; Teng, Shang-Hua (2014). "Fast lineare Zeitalgorithmen zur Vorkonditionierung und Lösung symmetrischer, diagonal dominanter linearer Systeme". Siam Journal über Matrixanalyse und Anwendungen. 35 (3): 835–885. Arxiv:CS/0607105. doi:10.1137/090771430. ISSN 0895-4798. S2CID 1750944.
  37. ^ Brookes, Stephen (2007). "Eine Semantik für die gleichzeitige Trennungslogik" (PDF). Theoretische Informatik. 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.
  38. ^ O'hearn, Peter (2007). "Ressourcen, Parallelität und lokale Argumentation" (PDF). Theoretische Informatik. 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035.
  39. ^ Dwork, Cynthia; McSerry, Frank; Nissim, Kobbi; Smith, Adam (2006). Halevi, Shai; Rabin, Tal (Hrsg.). Kalibrieren von Rauschen zur Empfindlichkeit in der privaten Datenanalyse. Theorie der Kryptographie (TCC). Vorlesungsnotizen in Informatik. Vol. 3876. Springer-Verlag. S. 265–284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.
  40. ^ Regev, Oded (2009). "Auf Gitter, Lernen mit Fehlern, zufälligen linearen Codes und Kryptographie". Journal of the ACM. 56 (6): 1–40. Citeseerx 10.1.1.215.3543. doi:10.1145/1568318.1568324. S2CID 207156623.
  41. ^ Dinur, Irit (2007). "Der PCP -Theorem durch Lückenverstärkung". Journal of the ACM. 54 (3): 12 - ES. doi:10.1145/1236457.1236459. S2CID 53244523.
  42. ^ "Ein konstruktiver Beweis für den allgemeinen Lovász Local Lemma". Journal of the ACM. 57 (2). 2010. doi:10.1145/1667053. ISSN 0004-5411.
  43. ^ Bulatov, Andrei A. (2013). "Die Komplexität des Problems der Zählbeschränkung". Journal of the ACM. Assoziation für Computermaschinen (ACM). 60 (5): 1–41. doi:10.1145/2528400. ISSN 0004-5411. S2CID 8964233.
  44. ^ Dyer, Martin; Richerby, David (2013). "Eine wirksame Dichotomie für das Problem der Zählbeschränkung". Siam Journal über Computing. Gesellschaft für industrielle und angewandte Mathematik (Siam). 42 (3): 1245–1274. Arxiv:1003.3879. doi:10.1137/100811258. ISSN 0097-5397. S2CID 1247279.
  45. ^ Cai, Jin-yi; Chen, XI (2017-06-22). "Komplexität des Zählens von CSP mit komplexen Gewichten". Journal of the ACM. Assoziation für Computermaschinen (ACM). 64 (3): 1–39. Arxiv:1111.2384. doi:10.1145/2822891. ISSN 0004-5411. S2CID 1053684.
  46. ^ Brakerski, Zvika; Vaikuntanathan, Vinod (Januar 2014). "Effiziente vollständig homomorphe Verschlüsselung von (Standard) $ \ mathsf {lwe} $". Siam Journal über Computing. 43 (2): 831–871. doi:10.1137/120868669. ISSN 0097-5397.
  47. ^ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "(Ausgeglichen) Voll homomorphe Verschlüsselung ohne Bootstrapping". Verfahren der 3. Innovationen in der theoretischen Informatikkonferenz über - ITCS '12. New York, New York, USA: ACM Press. doi:10.1145/2090236.2090262.

Siehe auch

Anmerkungen

  1. ^ "Der Gödel -Brief". 2009-02-12.
  2. ^ a b "2017 Gödel Prize". Europäische Vereinigung für theoretische Informatik. EATCS. Abgerufen 29. März 2017.
  3. ^ "Drei Papiere, die zur Grundlage des Wachstums der algorithmischen Spieltheorie zitiert werden", ". 16. Mai 2012. archiviert von das Original am 18. Juli 2013. Abgerufen 16. Mai 2012.
  4. ^ Die ACM Group präsentiert den Gödel -Preis für Fortschritte in der Kryptographie: Drei Informatiker für Innovationen, die die Sicherheit verbessern Archiviert 2013-06-01 im Wayback -Maschine, Verband für Rechenmaschinen, 29. Mai 2013.
  5. ^ Die Empfänger erzielten bahnbrechende Ergebnisse, um Daten aus mehreren Quellen zu aggregieren, Verband für Rechenmaschinen, 30. April 2014.
  6. ^ 2015 Gödel Prize -Ankündigung Archiviert 2017-12-09 bei der Wayback -Maschine durch Verband für Rechenmaschinen.
  7. ^ "2018 Gödel Prize Citation".
  8. ^ "2019 Gödel Prize Citation".
  9. ^ "2020 Gödel Preiszitat".
  10. ^ "2021 Gödel Preiszitation".
  11. ^ "2022 Gödel Preiszitation".

Verweise