جائزة گودل

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory (ACM SIGACT). The award is named in honor of Kurt 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 to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

The Gödel Prize has been awarded since 1993. The prize is awarded either at STOC (ACM Symposium on Theory of Computing, one of the main North American conferences in theoretical computer science) or ICALP (International Colloquium on Automata, Languages and Programming, one of the main European 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.

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.

الحائزون

Year	Name(s)	Notes	Publication year
1993	László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff	for the development of interactive proof systems	1988, 1989
1994	Johan Håstad	for an exponential lower bound on the size of constant-depth Boolean circuits (for the parity function).	1989
1995	Neil Immerman and Róbert Szelepcsényi	for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity	1988, 1988
1996	Mark Jerrum and Alistair Sinclair	for work on Markov chains and the approximation of the permanent of a matrix	1989, 1989
1997	Joseph Halpern and Yoram Moses	for defining a formal notion of "knowledge" in distributed environments	1990
1998	Seinosuke Toda	for Toda's theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)	1991
1999	Peter Shor	for Shor's algorithm for factoring numbers in polynomial time on a quantum computer	1997
2000	Moshe Y. Vardi and Pierre Wolper	for work on temporal logic with finite automata	1994
2001	Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy	for the PCP theorem and its applications to hardness of approximation	1996, 1998, 1998
2002	Géraud Sénizergues	for proving that equivalence of deterministic pushdown automata is decidable	2001
2003	Yoav Freund and Robert Schapire	for the AdaBoost algorithm in machine learning	1997
2004	Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou	for applications of topology to the theory of distributed computing	1999, 2000
2005	Noga Alon, Yossi Matias and Mario Szegedy	for their foundational contribution to streaming algorithms	1999
2006	Manindra Agrawal, Neeraj Kayal, Nitin Saxena	for the AKS primality test	2004
2007	Alexander Razborov, Steven Rudich	for natural proofs	1997
2008	Daniel Spielman, Shanghua Teng	for smoothed analysis of algorithms	2004
2009	Omer Reingold, Salil Vadhan, Avi Wigderson	for zig-zag product of graphs and undirected connectivity in log space	2002, 2008
2010	Sanjeev Arora, Joseph S. B. Mitchell	for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem (ETSP)	1998, 1999
2011	Johan Håstad	for proving optimal inapproximability result for various combinatorial problems	2001
2012	Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen (de), Tim Roughgarden and Éva Tardos	for laying the foundations of algorithmic game theory	2009, 2002, 2001
2013	Dan Boneh, Matthew K. Franklin, and Antoine Joux	for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography	2003, 2004
2014	Ronald Fagin, Amnon Lotem (fr), and Moni Naor	for Optimal Aggregation Algorithms for Middleware	2003,
2015	Daniel Spielman, Shanghua Teng	for their series of papers on nearly-linear-time Laplacian solvers	2011 2013 2014
2016	Stephen Brookes and Peter W. O'Hearn	for their invention of Concurrent Separation Logic	2007, 2007
2017	Cynthia Dwork, Frank McSherry (fr), Kobbi Nissim, and Adam D. Smith (fr)	for the invention of differential privacy	2006
2018	Oded Regev	for introducing the Learning with errors problem	2009
2019	Irit Dinur	for her new proof of the PCP theorem by gap amplification	2007
2020	Robin Moser and Gábor Tardos	for their constructive proof of the Lovász Local Lemma	2010

الأوراق البحثية الفائزة

^ Babai, László; Moran, Shlomo (1988), "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class", Journal of Computer and System Sciences 36 (2): 254–276, doi:10.1016/0022-0000(88)90028-1, ISSN 0022-0000, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf
^ Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems", SIAM Journal on Computing 18 (1): 186–208, doi:10.1137/0218012, ISSN 1095-7111, http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf
^ Håstad, Johan (1989), "Almost Optimal Lower Bounds for Small Depth Circuits", in Micali, Silvio, Randomness and Computation, Advances in Computing Research, 5, JAI Press, pp. 6–20, ISBN 978-0-89232-896-3, Archived from the original on 2012-02-22, http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf
^ Immerman, Neil (1988), "Nondeterministic space is closed under complementation", SIAM Journal on Computing 17 (5): 935–938, doi:10.1137/0217058, ISSN 1095-7111, http://www.cs.umass.edu/~immerman/pub/space.pdf
^ Szelepcsényi, R. (1988), "The method of forced enumeration for nondeterministic automata", Acta Informatica 26 (3): 279–284, doi:10.1007/BF00299636, http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf
^ 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
^ Jerrum, M.; Sinclair, Alistair (1989), "Approximating the permanent", SIAM Journal on Computing 18 (6): 1149–1178, doi:10.1137/0218077, ISSN 1095-7111
^ Halpern, Joseph; Moses, Yoram (1990), "Knowledge and common knowledge in a distributed environment", Journal of the ACM 37 (3): 549–587, doi:10.1145/79147.79161, https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf
^ Toda, Seinosuke (1991), "PP is as hard as the polynomial-time hierarchy", SIAM Journal on Computing 20 (5): 865–877, doi:10.1137/0220053, ISSN 1095-7111, http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf
^ 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, doi:10.1137/S0097539795293172, ISSN 1095-7111, http://physics.princeton.edu/~mcdonald/examples/QM/shor_siamjc_26_1484_97.pdf ^[]
^ Vardi, Moshe Y.; Wolper, Pierre (1994), "Reasoning about infinite computations", Information and Computation 115 (1): 1–37, doi:10.1006/inco.1994.1092, ISSN 0890-5401, Archived from the original on 2011-08-25, https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf
^ Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques", Journal of the ACM 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411, http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf
^ Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: a new characterization of NP", Journal of the ACM 45 (1): 70–122, doi:10.1145/273865.273901, ISSN 0004-5411, Archived from the original on 2011-06-10, https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf
^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM 45 (3): 501–555, doi:10.1145/278298.278306, ISSN 0004-5411, Archived from the original on 2011-06-10, https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf
^ 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
^ Freund, Y.; Schapire, R.E. (1997), "A decision-theoretic generalization of on-line learning and an application to boosting", Journal of Computer and System Sciences 55 (1): 119–139, doi:10.1006/jcss.1997.1504, ISSN 1090-2724, http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf
^ Herlihy, Maurice; Shavit, Nir (1999), "The topological structure of asynchronous computability", Journal of the ACM 46 (6): 858–923, doi:10.1145/331524.331529, http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf . Gödel prize lecture
^ Saks, Michael; Zaharoglou, Fotios (2000), "Wait-free k-set agreement is impossible: The topology of public knowledge", SIAM Journal on Computing 29 (5): 1449–1483, doi:10.1137/S0097539796307698
^ Alon, Noga; Matias, Yossi; Szegedy, Mario (1999), "The space complexity of approximating the frequency moments", Journal of Computer and System Sciences 58 (1): 137–147, doi:10.1006/jcss.1997.1545, http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf . First presented at the Symposium on Theory of Computing (STOC) in 1996.
^ 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, Archived from the original on 2011-06-07, https://web.archive.org/web/20110607101302/http://math.berkeley.edu/~coleman/Courses/Fall08/Cryptography/primality_v6.pdf
^ Razborov, Alexander A.; Rudich, Steven (1997), "Natural proofs", Journal of Computer and System Sciences 55 (1): 24–35, doi:10.1006/jcss.1997.1494, نطقب:ECCC, ISSN 0022-0000
^ 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, doi:10.1145/990308.990310, ISSN 0004-5411, http://eprints.kfupm.edu.sa/65442/1/65442.pdf ^[]
^ 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, doi:10.2307/3062153, ISSN 0003-486X, http://eprints.kfupm.edu.sa/37801/1/37801.pdf ^[]
^ Reingold, Omer (2008), "Undirected connectivity in log-space", J. ACM 55 (4): 1–24, doi:10.1145/1391289.1391291, ISSN 0004-5411, http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps ^[]
^ Arora, Sanjeev (1998), "Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems", Journal of the ACM 45 (5): 753–782, doi:10.1145/290179.290180, ISSN 0004-5411
^ 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
^ Håstad, Johan (2001), "Some optimal inapproximability results", Journal of the ACM 48 (4): 798–859, doi:10.1145/502090.502098, ISSN 0004-5411, http://www.nada.kth.se/~johanh/optimalinap.pdf
^ Koutsoupias, Elias; Papadimitriou, Christos (2009). "Worst-case equilibria". Computer Science Review. 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ (2006) "Calibrating Noise to Sensitivity in Private Data Analysis" in Theory of Cryptography (TCC). 3876: 265–284, Springer-Verlag. doi:10.1007/11681878_14.
^ 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.
^ Dinur, Irit (2007). "The PCP theorem by gap amplification". Journal of the ACM. 54 (3): 12–es. doi:10.1145/1236457.1236459.
^ "A constructive proof of the general Lovász Local Lemma". Journal of the ACM. 57 (2). 2010. doi:10.1145/1667053. ISSN 0004-5411.

انظر أيضاً

قائمة جوائز فهم الحاسب

الهامش

^ "The Gödel Letter". 2009-02-12.
^ "2017 Gödel Prize". European Association for Theoretical Computer Science. EATCS. Retrieved 29 March 2017.
^ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 May 2012. Archived from the original on 18 July 2013. Retrieved 16 May 2012.
^ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security Archived 2013-06-01 at the Wayback Machine., Association for Computing Machinery, May 29, 2013.
^ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
^ 2015 Gödel Prize announcement Archived 2017-12-09 at the Wayback Machine. by Association for Computing Machinery.
^ "2018 Gödel Prize citation".
^ "2019 Gödel Prize citation".
^ "2020 Gödel Prize citation".