Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Gödel Prize

From Wikipedia, the free encyclopedia
Computer science award
Not to be confused with theGödel Lecture.
Kurt Gödel
Kurt Gödel

TheGödel Prize is an annual prize for outstanding papers in the area oftheoretical computer science, given jointly by theEuropean Association for Theoretical Computer Science (EATCS) and theAssociation for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The award is named in honor ofKurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter toJohn von Neumann in which Gödel asked whether a certainNP-complete problem could be solved inquadratic orlinear time.[1]

The Gödel Prize has been awarded since 1993. The prize is awarded alternately at ICALP (even years) and STOC (odd years). STOC is the ACMSymposium on Theory of Computing, one of the mainNorth American conferences in theoretical computer science, whereas ICALP is theInternational Colloquium on Automata, Languages and Programming, one of the mainEuropean conferences in the field. To be eligible for the prize, a paper must be published in a refereed journal within the last 14 (formerly 7) years. The prize includes a reward of US$5000.[2]

The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT.

In contrast with the Gödel Prize, which recognizes outstanding papers, theKnuth Prize is awarded to individuals for their overall impact in the field.

Recipients

[edit]
YearName(s)NotesPublication year
1993László Babai,Shafi Goldwasser,Silvio Micali,Shlomo Moran, andCharles Rackofffor the development ofinteractive proof systems1988,[paper 1] 1989[paper 2]
1994Johan Håstadfor an exponentiallower bound onthe size of constant-depthBoolean circuits (for theparity function).1989[paper 3]
1995Neil Immerman andRóbert Szelepcsényifor theImmerman–Szelepcsényi theorem regarding nondeterministic space complexity1988,[paper 4] 1988[paper 5]
1996Mark Jerrum andAlistair Sinclairfor work onMarkov chains and the approximation of thepermanent of a matrix1989,[paper 6] 1989[paper 7]
1997Joseph Halpern andYoram Mosesfor defining a formal notion of "knowledge" in distributed environments1990[paper 8]
1998Seinosuke TodaforToda's theorem, which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)1991[paper 9]
1999Peter ShorforShor's algorithm forfactoring numbers inpolynomial time on aquantum computer1997[paper 10]
2000Moshe Y. Vardi andPierre Wolperfor work ontemporal logic withfinite automata1994[paper 11]
2001Sanjeev Arora,Uriel Feige,Shafi Goldwasser,Carsten Lund,László Lovász,Rajeev Motwani,Shmuel Safra,Madhu Sudan, andMario Szegedyfor thePCP theorem and its applications to hardness of approximation1996,[paper 12] 1998,[paper 13] 1998[paper 14]
2002Géraud Sénizerguesfor proving that equivalence ofdeterministic pushdown automata isdecidable2001[paper 15]
2003Yoav Freund andRobert Schapirefor theAdaBoost algorithm inmachine learning1997[paper 16]
2004Maurice Herlihy,Michael Saks,Nir Shavit andFotios Zaharogloufor applications oftopology to the theory ofdistributed computing1999,[paper 17] 2000[paper 18]
2005Noga Alon,Yossi Matias andMario Szegedyfor their foundational contribution tostreaming algorithms1999[paper 19]
2006Manindra Agrawal,Neeraj Kayal,Nitin Saxenafor theAKS primality test2004[paper 20]
2007Alexander Razborov,Steven Rudichfornatural proofs1997[paper 21]
2008Daniel Spielman,Shang-Hua Tengforsmoothed analysis of algorithms2004[paper 22]
2009Omer Reingold,Salil Vadhan,Avi Wigdersonforzig-zag product ofgraphs andundirected connectivity inlog space2002,[paper 23] 2008[paper 24]
2010Sanjeev Arora,Joseph S. B. Mitchellfor their concurrent discovery of apolynomial-time approximation scheme for the EuclideanTravelling Salesman Problem1998,[paper 25] 1999[paper 26]
2011Johan Håstadfor proving optimal inapproximability results for various combinatorial problems2001[paper 27]
2012Elias Koutsoupias,Christos Papadimitriou,Noam Nisan,Amir Ronen,Tim Roughgarden andÉva Tardosfor laying the foundations ofalgorithmic game theory[3]2009,[paper 28] 2002,[paper 29] 2001[paper 30]
2013Dan Boneh,Matthew K. Franklin, andAntoine Jouxfor multi-partyDiffie–Hellman key exchange and theBoneh–Franklin scheme in cryptography[4]2003,[paper 31]

2004[paper 32]

2014Ronald Fagin,Amnon Lotem [fr], andMoni Naorfor Optimal Aggregation Algorithms formiddleware[5]2003,[paper 33]
2015Daniel Spielman,Shang-Hua Tengfor their series of papers on nearly-linear-time Laplacian solvers[6]

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

2016Stephen Brookes andPeter W. O'Hearnfor their invention ofConcurrent Separation Logic2007,[paper 37] 2007[paper 38]
2017[2]Cynthia Dwork,Frank McSherry,Kobbi Nissim, andAdam D. Smithfor the invention ofdifferential privacy2006[paper 39]
2018[7]Oded Regevfor introducing thelearning with errors problem2009[paper 40]
2019[8]Irit Dinurfor her new proof of thePCP theorem by gap amplification2007[paper 41]
2020[9]Robin Moser andGábor Tardosfor theirconstructive proof of theLovász local lemma2010[paper 42]
2021[10]Andrei Bulatov,Jin-Yi Cai,Xi Chen,Martin Dyer, and David Richerbyfor their work on the classification of thecounting complexity ofconstraint satisfaction problems2013[paper 43] 2013[paper 44] 2017[paper 45]
2022[11]Zvika Brakerski,Craig Gentry, andVinod Vaikuntanathanfor their transformative contributions to cryptography by constructing efficient fullyhomomorphic encryption (FHE) schemes2014,[paper 46] 2014[paper 47]
2023[12]Samuel Fiorini,Serge Massar, andSebastian Pokutta,Hans Raj Tiwary,Ronald de Wolf, andThomas Rothvossfor showing that any extended formulation for theTSP polytope has exponential size2015,[paper 48] 2017[paper 49]
2024[13]Ryan Williamsfor his work oncircuit lower bounds and the “algorithms to lower bounds” paradigm2011[paper 50]

Winning papers

[edit]
  1. ^Babai, László; Moran, Shlomo (1988),"Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class"(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),"The knowledge complexity of interactive proof systems"(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),"Almost Optimal Lower Bounds for Small Depth Circuits"(PDF), in Micali, Silvio (ed.),Randomness and Computation, Advances in Computing Research, vol. 5, JAI Press, pp. 6–20,ISBN 978-0-89232-896-3, archived fromthe original(PDF) on 2012-02-22
  4. ^Immerman, Neil (1988),"Nondeterministic space is closed under complementation"(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),"The method of forced enumeration for nondeterministic automata"(PDF),Acta Informatica,26 (3):279–284,doi:10.1007/BF00299636,hdl:10338.dmlcz/120489,S2CID 10838178
  6. ^Sinclair, A.; Jerrum, M. (1989), "Approximate counting, uniform generation and rapidly mixing Markov chains",Information and Computation,82 (1):93–133,doi:10.1016/0890-5401(89)90067-9,ISSN 0890-5401
  7. ^Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent",SIAM Journal on Computing,18 (6):1149–1178,CiteSeerX 10.1.1.431.4190,doi:10.1137/0218077,ISSN 1095-7111
  8. ^Halpern, Joseph;Moses, Yoram (1990),"Knowledge and common knowledge in a distributed environment"(PDF),Journal of the ACM,37 (3):549–587,arXiv:cs/0006009,doi:10.1145/79147.79161,S2CID 52151232
  9. ^Toda, Seinosuke (1991),"PP is as hard as the polynomial-time hierarchy"(PDF),SIAM Journal on Computing,20 (5):865–877,CiteSeerX 10.1.1.121.1246,doi:10.1137/0220053,ISSN 1095-7111, archived fromthe original(PDF) on 2016-03-03, retrieved2010-06-08
  10. ^Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer",SIAM Journal on 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),"Reasoning about infinite computations"(PDF),Information and Computation,115 (1):1–37,doi:10.1006/inco.1994.1092,ISSN 0890-5401, archived fromthe original(PDF) on 2011-08-25
  12. ^Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996),"Interactive proofs and the hardness of approximating cliques"(PDF),Journal of the ACM,43 (2):268–292,doi:10.1145/226643.226652,ISSN 0004-5411
  13. ^Arora, Sanjeev; Safra, Shmuel (1998),"Probabilistic checking of proofs: a new characterization of NP"(PDF),Journal of the ACM,45 (1):70–122,doi:10.1145/273865.273901,ISSN 0004-5411,S2CID 751563, archived fromthe original(PDF) on 2011-06-10
  14. ^Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998),"Proof verification and the hardness of approximation problems"(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, archived fromthe original(PDF) on 2011-06-10
  15. ^Sénizergues, Géraud (2001), "L(A) = L(B)? decidability results from complete formal systems",Theor. Comput. Sci.,251 (1):1–166,doi:10.1016/S0304-3975(00)00285-1,ISSN 0304-3975
  16. ^Freund, Y.; Schapire, R.E. (1997),"A decision-theoretic generalization of on-line learning and an application to boosting"(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),"The topological structure of asynchronous computability"(PDF),Journal of the ACM,46 (6):858–923,CiteSeerX 10.1.1.78.1455,doi:10.1145/331524.331529,S2CID 5797174.Gödel prize lecture
  18. ^Saks, Michael;Zaharoglou, Fotios (2000), "Wait-freek-set agreement is impossible: The topology of public knowledge",SIAM Journal on Computing,29 (5):1449–1483,doi:10.1137/S0097539796307698
  19. ^Alon, Noga; Matias, Yossi; Szegedy, Mario (1999),"The space complexity of approximating the frequency moments"(PDF),Journal of Computer and System Sciences,58 (1):137–147,doi:10.1006/jcss.1997.1545. First presented at theSymposium on Theory of Computing (STOC) in 1996.
  20. ^Agrawal, M.; Kayal, N.; Saxena, N. (2004), "PRIMES is in P",Annals of Mathematics,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/jcss.1997.1494,ISSN 0022-0000,ECCC TR94-010
  22. ^Spielman, Daniel A.;Teng, Shang-Hua (2004), "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time",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, the zig-zag graph product, and new constant-degree expanders",Annals of Mathematics,155 (1):157–187,CiteSeerX 10.1.1.236.8669,doi:10.2307/3062153,ISSN 0003-486X,JSTOR 3062153,MR 1888797,S2CID 120739405
  24. ^Reingold, Omer (2008),"Undirected connectivity in log-space",J. ACM,55 (4):1–24,doi:10.1145/1391289.1391291,ISSN 0004-5411,S2CID 207168478[permanent dead link‍]
  25. ^Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems",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 Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation 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),"Some optimal inapproximability results"(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 equilibria".Computer Science Review.3 (2):65–69.doi:10.1016/j.cosrev.2009.04.003.
  29. ^Roughgarden, Tim; Tardos, Éva (2002). "How bad is selfish 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). "Algorithmic Mechanism Design".Games and Economic Behavior.35 (1–2):166–196.CiteSeerX 10.1.1.21.1731.doi:10.1006/game.1999.0790.
  31. ^Boneh, Dan; Franklin, Matthew (2003). "Identity-based encryption from the Weil pairing".SIAM Journal on Computing.32 (3):586–615.CiteSeerX 10.1.1.66.1131.doi:10.1137/S0097539701398521.MR 2001745.
  32. ^Joux, Antoine (2004)."A one round protocol for tripartite Diffie-Hellman".Journal of Cryptology.17 (4):263–276.doi:10.1007/s00145-004-0312-y.MR 2090557.S2CID 3350730.
  33. ^Fagin, Ronald; Lotem, Amnon; Naor, Moni (2003). "Optimal aggregation algorithms for 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). "Spectral Sparsification of Graphs".SIAM Journal on 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). "A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning".SIAM Journal on 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). "Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems".SIAM Journal on Matrix Analysis and Applications.35 (3):835–885.arXiv:cs/0607105.doi:10.1137/090771430.ISSN 0895-4798.S2CID 1750944.
  37. ^Brookes, Stephen (2007)."A Semantics for Concurrent Separation Logic"(PDF).Theoretical Computer Science.375 (1–3):227–270.doi:10.1016/j.tcs.2006.12.034.
  38. ^O'Hearn, Peter (2007)."Resources, Concurrency and Local Reasoning"(PDF).Theoretical Computer Science.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.).Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science. Vol. 3876. Springer-Verlag. pp. 265–284.doi:10.1007/11681878_14.ISBN 978-3-540-32731-8.
  40. ^Regev, Oded (2009). "On lattices, learning with errors, random linear codes, and cryptography".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)."The PCP theorem by gap amplification".Journal of the ACM.54 (3): 12–es.doi:10.1145/1236457.1236459.S2CID 53244523.
  42. ^"A constructive proof of the general Lovász Local Lemma".Journal of the ACM.57 (2). 2010.doi:10.1145/1667053.ISSN 0004-5411.
  43. ^Bulatov, Andrei A. (2013). "The complexity of the counting constraint satisfaction problem".Journal of the ACM.60 (5). Association for Computing Machinery:1–41.doi:10.1145/2528400.ISSN 0004-5411.S2CID 8964233.
  44. ^Dyer, Martin; Richerby, David (2013). "An Effective Dichotomy for the Counting Constraint Satisfaction Problem".SIAM Journal on Computing.42 (3). Society for Industrial & Applied Mathematics (SIAM):1245–1274.arXiv:1003.3879.doi:10.1137/100811258.ISSN 0097-5397.S2CID 1247279.
  45. ^Cai, Jin-Yi; Chen, Xi (2017-06-22). "Complexity of Counting CSP with Complex Weights".Journal of the ACM.64 (3). Association for Computing Machinery:1–39.arXiv:1111.2384.doi:10.1145/2822891.ISSN 0004-5411.S2CID 1053684.
  46. ^Brakerski, Zvika; Vaikuntanathan, Vinod (January 2014)."Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$".SIAM Journal on Computing.43 (2):831–871.doi:10.1137/120868669.hdl:1721.1/115488.ISSN 0097-5397.S2CID 8831240.
  47. ^Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012)."(Leveled) fully homomorphic encryption without bootstrapping".Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York, New York, USA: ACM Press. pp. 309–325.doi:10.1145/2090236.2090262.ISBN 9781450311151.S2CID 2602543.
  48. ^Fiorini, Samuel; Massar, Serge; Pokutta, Sebastian; Tiwary, Hans Raj; de Wolf, Ronald (2015)."Exponential Lower Bounds for Polytopes in Combinatorial Optimization".Journal of the ACM.62 (2): 17:1–17:23.arXiv:1111.0837.doi:10.1145/2716307.S2CID 7372000.
  49. ^Rothvoss, Thomas (2017)."The Matching Polytope has Exponential Extension Complexity".Journal of the ACM.64 (6): 41:1–41:19.arXiv:1311.2369.doi:10.1145/3127497.S2CID 47045361.
  50. ^Williams, Ryan (June 2011)."Non-uniform ACC Circuit Lower Bounds".2011 IEEE 26th Annual Conference on Computational Complexity. IEEE. pp. 115–125.doi:10.1109/ccc.2011.36.ISBN 978-1-4577-0179-5.

See also

[edit]

Notes

[edit]
  1. ^"The Gödel Letter". 2009-02-12.
  2. ^ab"2017 Gödel Prize".European Association for Theoretical Computer Science. EATCS. Retrieved29 March 2017.
  3. ^"Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Archived fromthe original on 18 July 2013. Retrieved16 May 2012.
  4. ^ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve SecurityArchived 2013-06-01 at theWayback Machine,Association for Computing Machinery, May 29, 2013.
  5. ^Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources,Association for Computing Machinery, April 30, 2014.
  6. ^2015 Gödel Prize announcementArchived 2017-12-09 at theWayback Machine byAssociation for Computing Machinery.
  7. ^"2018 Gödel Prize citation".
  8. ^"2019 Gödel Prize citation".
  9. ^"2020 Gödel Prize citation".
  10. ^"2021 Gödel Prize citation".
  11. ^Chita, Efi."2022 Gödel Prize citation".EATCS.
  12. ^Chita, Efi."2023 Gödel Prize citation".EATCS.
  13. ^"2024 Gödel Prize citation".

References

[edit]
Gödel Prize laureates
Special Interest Groups
Awards
ACM
SIGs
Publications
Conferences
Educational programs
Retrieved from "https://en.wikipedia.org/w/index.php?title=Gödel_Prize&oldid=1282400885"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp