哥德爾獎

哥德爾獎（英語：Gödel Prize）是一個頒發給理論計算機科學領域傑出論文的年度獎項，由歐洲理論計算機科學協會（英語：European Association for Theoretical Computer Science）（EATCS）和美國計算機協會算法和計算理論特別興趣小組（計算機協會算法和計算理論特別興趣小組（英語：ACM SIGACT））聯合頒發。該獎項是為紀念庫爾特·哥德爾而命名的。哥德爾是第一個提出P/NP問題的人，在1956年寫給約翰·馮·諾伊曼的信中，哥德爾問某個NP完全的問題是否可以用二次或是線性時間來解決^[1]。

哥德爾獎於1993年開始在STOC（ACM計算理論研討會（英語：Symposium on Theory of Computing），北美理論計算機科學的主要會議之一）或ICALP（自動機、語言和編程國際座談會（英語：International Colloquium on Automata, Languages and Programming），該領域的主要歐洲會議之一）上頒發。獲獎論文必須在理論計算機領域具有開創性重大貢獻，同時需在獲獎前14年內在學術期刊上正式發表。該獎項包括5,000美元的獎金^[2]。

哥德爾獎的評審委員會由6名成員組成，分別由EATCS主席和SIGACT主席各提名三名成員，任期三年並交錯進行。委員會由EATCS和SIGACT的代表輪流擔任主席。

獲獎者

年份	獲獎者	原因	發表時間
1993	拉斯洛·鮑鮑伊（英語：László Babai）、莎菲·戈德瓦塞爾、希爾維奧·米卡利、什洛莫·莫蘭（英語：Shlomo Moran）、查爾斯·拉克福（英語：Charles Rackoff）	表彰其開發交互式證明系統	1988[paper 1] 1989[paper 2]
1994	約翰·哈斯塔德（英語：Johan Håstad）	表彰其證明恆深布林電路（英語：Boolean circuit）大小的指數下界（對於奇偶函數（英語：Parity function））	1989[paper 3]
1995	尼爾·伊莫曼（英語：Neil Immerman）、羅伯特·塞萊普切尼（英語：Róbert Szelepcsényi）	表彰其證明非決定性空間複雜性的伊莫曼-塞萊普切尼定理（英語：Immerman–Szelepcsényi theorem）	1988[paper 4] 1988[paper 5]
1996	馬克·傑魯姆（英語：Mark Jerrum）、阿利斯泰爾·辛克萊爾	表彰其在馬可夫鏈和矩陣積和式的近似方面的工作	1989[paper 6] 1989[paper 7]
1997	約瑟夫·哈爾彭（英語：Joseph Halpern）、約拉姆·莫塞斯（英語：Yoram Moses）	表彰其為分佈式環境中的「知識」定義一個正式的概念	1990[paper 8]
1998	戶田誠之助（日語：戸田誠之助）	表彰其證明顯示計數解（PP）和量詞交替（PH）之間的關聯的戶田定理	1991[paper 9]
1999	彼得·秀爾	表彰其開發在量子計算機上以多項式時間計算整數分解的秀爾算法	1997[paper 10]
2000	摩西·瓦迪（英語：Moshe Vardi）、皮埃爾·沃爾珀（英語：Pierre Wolper）	表彰其在有限狀態機的時間邏輯方面的工作	1994[paper 11]
2001	桑吉夫·阿羅拉（英語：Sanjeev Arora）、烏列爾·費奇（英語：Uriel Feige）、莎菲·戈德瓦塞爾、卡斯坦·隆德（英語：Carsten Lund）、洛瓦茲·拉茲洛、拉耶夫·莫特瓦尼（英語：Rajeev Motwani）、什穆埃爾·沙夫拉（英語：Shmuel Safra）、邁度·蘇丹（英語：Madhu Sudan）、馬里奧·塞格德（英語：Mario Szegedy）	表彰其證明PCP定理（英語：PCP theorem）以及在近似硬度方面的應用	1996[paper 12] 1998[paper 13] 1998[paper 14]
2002	傑霍·賽尼澤格（英語：Géraud Sénizergues）	表彰其證明確定下推自動機的等價性是可決定（英語：Decidability (logic)）的	2001[paper 15]
2003	約阿夫·弗羅因德、羅伯特·沙皮爾	表彰其開發機器學習中的AdaBoost算法	1997[paper 16]
2004	莫里斯·赫利希（英語：Maurice Herlihy）、麥可·薩克斯（英語：Michael Saks (mathematician)）、尼爾·沙維特（英語：Nir Shavit）、弗蒂奧斯·札哈羅格羅（英語：Fotios Zaharoglou）	表彰其在拓撲學在分佈式計算理論中的應用	1999[paper 17] 2000[paper 18]
2005	諾加·阿隆、約西·馬蒂亞斯（英語：Yossi Matias）、馬里奧·塞格德（英語：Mario Szegedy）	表彰其對Streaming algorithm（英語：串流演算法）的基礎性貢獻	1999[paper 19]
2006	曼寧德拉·阿格拉瓦爾（英語：Manindra Agrawal）、尼拉吉·卡亞爾（英語：Neeraj Kayal）、尼汀·沙克謝納（英語：Nitin Saxena）	表彰其開發AKS質數測試	2004[paper 20]
2007	亞歷山大·拉茲波洛夫（英語：Alexander Razborov）、史蒂芬·魯迪奇（英語：Steven Rudich）	表彰其提出 自然證明（英語：Natural proof）	1997[paper 21]
2008	丹尼爾·斯皮爾曼（英語：Daniel Spielman）、滕尚華	表彰其開發算法的平滑分析（英語：Smoothed analysis）	2004[paper 22]
2009	奧馬爾·萊因戈爾德（英語：Omer Reingold）、薩利爾·瓦德漢（英語：Salil Vadhan）、阿維·威格森	表彰其證明圖的鋸齒乘積（英語：Zig-zag product）和對數空間中的無定向連接性	2002[paper 23] 2008[paper 24]
2010	桑吉夫·阿羅拉（英語：Sanjeev Arora）、約瑟夫·S·B·米切爾（英語：Joseph S. B. Mitchell）	表彰其發現歐幾里得旅行推銷員問題（ETSP）的多項式時間近似算法（PTAS）	1998[paper 25] 1999[paper 26]
2011	約翰·哈斯塔德（英語：Johan Håstad）	表彰其證明各種組合問題的最佳非近似性結果	2001[paper 27]
2012	埃利亞斯·庫特索皮亞斯（英語：Elias Koutsoupias）、赫里斯托斯·帕帕季米特里烏、諾姆·尼散、阿米爾·羅能（Amir Ronen）、提姆·羅加登（英語：Tim Roughgarden）、陶爾多什·埃娃	表彰其奠定算法博弈論（英語：Algorithmic game theory）的基礎[3]	2009[paper 28] 2001[paper 29] 2002[paper 30]
2013	丹·博內、馬修·K·富蘭克林（英語：Matthew K. Franklin）、安托萬·朱斯（英語：Antoine Joux）	表彰其開發多方迪菲-赫爾曼密鑰交換和密碼學中的博內-富蘭克林法（英語：Boneh–Franklin scheme）[4]	2003[paper 31] 2004[paper 32]
2014	羅納德·法金（英語：Ronald Fagin）、阿姆農·洛特姆（Amnon Lotem）、莫尼·瑙爾（英語：Moni Naor）	表彰其開發中介軟體的最佳集合算法[5]	2003[paper 33]
2015	丹尼爾·斯皮爾曼（英語：Daniel Spielman）、滕尚華	表彰其開發近線性時間的拉普拉斯求解器[6]	2011[paper 34] 2013[paper 35] 2014[paper 36]
2016	史蒂芬·布魯克斯（Stephen Brookes）、彼得·歐赫恩（英語：Peter O'Hearn）	表彰其開發並行分離邏輯（英語：Separation logic）	2007[paper 37] 2007[paper 38]
2017[2]	辛西婭·德沃克（英語：Cynthia Dwork）、弗蘭克·麥克謝里（英語：Frank McSherry）、科比·尼西姆（英語：Kobbi Nissim）、亞當·D·史密斯（英語：Adam D. Smith）	表彰其開發差分隱私	2006[paper 39]
2018[7]	歐德德·瑞格夫（英語：Oded Regev (computer scientist)）	表彰其介紹容錯學習問題	2009[paper 40]
2019[8]	伊里特·迪努爾（英語：Irit Dinur）	表彰其利用間隙放大法重新證明PCP定理（英語：PCP theorem）	2007[paper 41]
2020[9]	羅賓·莫瑟（Robin Moser）、陶爾多什·加博爾（英語：Gábor Tardos）	表彰其對拉茲洛局部定理（英語：Lovász local lemma）的建設性證明（英語：Algorithmic Lovász local lemma）	2010[paper 42]
2021[10]	安德烈·布拉托夫（Andrei Bulatov）、蔡進一（英語：Jin-Yi Cai）、陳汐（英語：Xi Chen）、馬丁·戴爾（英語：Martin Dyer）、大衛·里切爾比（David Richerby）	表彰其在約束滿足問題的計數複雜性（英語：Counting problem (complexity)）分類方面的工作	2013[paper 43] 2013[paper 44] 2017[paper 45]
2022[11]	茲維卡·布拉克斯基（Zvika Brakerski）、克雷格·金特里（英語：Craig Gentry (computer scientist)）、維諾德·維昆塔森（Vinod Vaikuntanathan）	表彰其通過構建高效的全同態加密（FHE）法對密碼學的變革性貢獻	2014[paper 46] 2014[paper 47]

獲獎論文

1. Babai, László; Moran, Shlomo, Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class (PDF), Journal of Computer and System Sciences, 1988, 36 (2): 254–276 [2022-10-31], ISSN 0022-0000, doi:10.1016/0022-0000(88)90028-1 , （原始內容存檔 (PDF)於2011-07-06）
2. Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems (PDF), SIAM Journal on Computing, 1989, 18 (1): 186–208 [2022-10-31], CiteSeerX 10.1.1.397.4002 , ISSN 1095-7111, doi:10.1137/0218012, （原始內容存檔 (PDF)於2011-09-27）
3. Håstad, Johan, Almost Optimal Lower Bounds for Small Depth Circuits (PDF), Micali, Silvio (編), Randomness and Computation, Advances in Computing Research 5, JAI Press: 6–20, 1989, ISBN 978-0-89232-896-3, （原始內容 (PDF)存檔於2012-02-22）
4. Immerman, Neil, Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, 1988, 17 (5): 935–938 [2022-10-31], CiteSeerX 10.1.1.54.5941 , ISSN 1095-7111, doi:10.1137/0217058, （原始內容存檔 (PDF)於2012-02-07）
5. Szelepcsényi, R., The method of forced enumeration for nondeterministic automata (PDF), Acta Informatica, 1988, 26 (3): 279–284 [2022-10-31], S2CID 10838178, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489, （原始內容存檔 (PDF)於2022-08-01）
6. Sinclair, A.; Jerrum, M., Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, 1989, 82 (1): 93–133, ISSN 0890-5401, doi:10.1016/0890-5401(89)90067-9
7. Jerrum, M.; Sinclair, Alistair, Approximating the permanent, SIAM Journal on Computing, 1989, 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 , ISSN 1095-7111, doi:10.1137/0218077
8. Halpern, Joseph; Moses, Yoram, Knowledge and common knowledge in a distributed environment (PDF), Journal of the ACM, 1990, 37 (3): 549–587 [2022-10-31], S2CID 52151232, arXiv:cs/0006009 , doi:10.1145/79147.79161, （原始內容存檔 (PDF)於2019-02-02）
9. Toda, Seinosuke, PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing, 1991, 20 (5): 865–877 [2022-10-31], CiteSeerX 10.1.1.121.1246 , ISSN 1095-7111, doi:10.1137/0220053, （原始內容 (PDF)存檔於2016-03-03）
10. Shor, Peter W., Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, 1997, 26 (5): 1484–1509, ISSN 1095-7111, S2CID 2337707, arXiv:quant-ph/9508027 , doi:10.1137/S0097539795293172
11. Vardi, Moshe Y.; Wolper, Pierre, Reasoning about infinite computations (PDF), Information and Computation, 1994, 115 (1): 1–37, ISSN 0890-5401, doi:10.1006/inco.1994.1092, （原始內容 (PDF)存檔於2011-08-25）
12. Feige, Uriel; Goldwasser, Shafi; Lovász, Laszlo; Safra, Shmuel; Szegedy, Mario, Interactive proofs and the hardness of approximating cliques (PDF), Journal of the ACM, 1996, 43 (2): 268–292 [2022-10-31], ISSN 0004-5411, doi:10.1145/226643.226652 , （原始內容存檔 (PDF)於2011-06-10）
13. Arora, Sanjeev; Safra, Shmuel, Probabilistic checking of proofs: a new characterization of NP (PDF), Journal of the ACM, 1998, 45 (1): 70–122, ISSN 0004-5411, S2CID 751563, doi:10.1145/273865.273901, （原始內容 (PDF)存檔於2011-06-10）
14. Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario, Proof verification and the hardness of approximation problems (PDF), Journal of the ACM, 1998, 45 (3): 501–555, CiteSeerX 10.1.1.145.4652 , ISSN 0004-5411, S2CID 8561542, doi:10.1145/278298.278306, （原始內容 (PDF)存檔於2011-06-10）
15. Sénizergues, Géraud, L(A) = L(B)? decidability results from complete formal systems, Theor. Comput. Sci., 2001, 251 (1): 1–166, ISSN 0304-3975, doi:10.1016/S0304-3975(00)00285-1 
16. Freund, Y.; Schapire, R.E., A decision-theoretic generalization of on-line learning and an application to boosting (PDF), Journal of Computer and System Sciences, 1997, 55 (1): 119–139 [2022-10-31], ISSN 1090-2724, doi:10.1006/jcss.1997.1504, （原始內容存檔 (PDF)於2011-07-19）
17. Herlihy, Maurice; Shavit, Nir, The topological structure of asynchronous computability (PDF), Journal of the ACM, 1999, 46 (6): 858–923 [2022-10-31], CiteSeerX 10.1.1.78.1455 , S2CID 5797174, doi:10.1145/331524.331529, （原始內容存檔 (PDF)於2011-06-05）. Gödel prize lecture （頁面存檔備份，存於網際網路檔案館）
18. Saks, Michael; Zaharoglou, Fotios, Wait-free k-set agreement is impossible: The topology of public knowledge, SIAM Journal on Computing, 2000, 29 (5): 1449–1483, doi:10.1137/S0097539796307698
19. Alon, Noga; Matias, Yossi; Szegedy, Mario, The space complexity of approximating the frequency moments (PDF), Journal of Computer and System Sciences, 1999, 58 (1): 137–147, doi:10.1006/jcss.1997.1545. First presented at the Symposium on Theory of Computing (STOC) in 1996.
20. Agrawal, M.; Kayal, N.; Saxena, N., PRIMES is in P, Annals of Mathematics, 2004, 160 (2): 781–793, ISSN 0003-486X, doi:10.4007/annals.2004.160.781 
21. Razborov, Alexander A.; Rudich, Steven, Natural proofs, Journal of Computer and System Sciences, 1997, 55 (1): 24–35, ISSN 0022-0000, doi:10.1006/jcss.1997.1494 
22. Spielman, Daniel A.; Teng, Shang-Hua, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, J. ACM, 2004, 51 (3): 385–463, ISSN 0004-5411, arXiv:math/0212413 , doi:10.1145/990308.990310
23. Reingold, Omer; Vadhan, Salil; Wigderson, Avi, Entropy waves, the zig-zag graph product, and new constant-degree expanders, Annals of Mathematics, 2002, 155 (1): 157–187, CiteSeerX 10.1.1.236.8669 , ISSN 0003-486X, JSTOR 3062153, MR 1888797, S2CID 120739405, doi:10.2307/3062153
24. Reingold, Omer, Undirected connectivity in log-space, J. ACM, 2008, 55 (4): 1–24 [2022-10-31], ISSN 0004-5411, S2CID 207168478, doi:10.1145/1391289.1391291, （原始內容存檔於2011-06-12）
25. Arora, Sanjeev, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM, 1998, 45 (5): 753–782, CiteSeerX 10.1.1.23.6765 , ISSN 0004-5411, S2CID 3023351, doi:10.1145/290179.290180
26. Mitchell, Joseph S. B., Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, 1999, 28 (4): 1298–1309, ISSN 1095-7111, doi:10.1137/S0097539796309764
27. Håstad, Johan, Some optimal inapproximability results (PDF), Journal of the ACM, 2001, 48 (4): 798–859 [2022-10-31], CiteSeerX 10.1.1.638.2808 , ISSN 0004-5411, S2CID 5120748, doi:10.1145/502090.502098, （原始內容存檔 (PDF)於2012-03-12）
28. Koutsoupias, Elias; Papadimitriou, Christos. Worst-case equilibria. Computer Science Review. 2009, 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
29. Nisan, Noam; Ronen, Amir. Algorithmic Mechanism Design. Games and Economic Behavior. 2001, 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . doi:10.1006/game.1999.0790.
30. Roughgarden, Tim; Tardos, Éva. How bad is selfish routing?. Journal of the ACM. 2002, 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . S2CID 207638789. doi:10.1145/506147.506153.
31. Boneh, Dan; Franklin, Matthew. Identity-based encryption from the Weil pairing. SIAM Journal on Computing. 2003, 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . MR 2001745. doi:10.1137/S0097539701398521.
32. Joux, Antoine. A one round protocol for tripartite Diffie-Hellman. Journal of Cryptology. 2004, 17 (4): 263–276. MR 2090557. S2CID 3350730. doi:10.1007/s00145-004-0312-y.
33. Fagin, Ronald; Lotem, Amnon; Naor, Moni. Optimal aggregation algorithms for middleware. Journal of Computer and System Sciences. 2003, 66 (4): 614–656. arXiv:cs/0204046 . doi:10.1016/S0022-0000(03)00026-6.
34. Spielman, Daniel A.; Teng, Shang-Hua. Spectral Sparsification of Graphs. SIAM Journal on Computing. 2011, 40 (4): 981–1025. ISSN 0097-5397. S2CID 9646279. arXiv:0808.4134 . doi:10.1137/08074489X.
35. Spielman, Daniel A.; Teng, Shang-Hua. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on Computing. 2013, 42 (1): 1–26. ISSN 0097-5397. S2CID 9151077. arXiv:0809.3232 . doi:10.1137/080744888.
36. Spielman, Daniel A.; Teng, Shang-Hua. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal on Matrix Analysis and Applications. 2014, 35 (3): 835–885. ISSN 0895-4798. S2CID 1750944. arXiv:cs/0607105 . doi:10.1137/090771430.
37. Brookes, Stephen. A Semantics for Concurrent Separation Logic (PDF). Theoretical Computer Science. 2007, 375 (1–3): 227–270 [2022-10-31]. doi:10.1016/j.tcs.2006.12.034. （原始內容存檔 (PDF)於2021-05-09）.
38. O'Hearn, Peter. Resources, Concurrency and Local Reasoning (PDF). Theoretical Computer Science. 2007, 375 (1–3): 271–307 [2022-10-31]. doi:10.1016/j.tcs.2006.12.035 . （原始內容存檔 (PDF)於2021-03-04）.
39. Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam. Halevi, Shai; Rabin, Tal , 編. Calibrating Noise to Sensitivity in Private Data Analysis. Theory of Cryptography (TCC). Lecture Notes in Computer Science 3876. Springer-Verlag: 265–284. 2006. ISBN 978-3-540-32731-8. doi:10.1007/11681878_14 .
40. Regev, Oded. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM. 2009, 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . S2CID 207156623. doi:10.1145/1568318.1568324.
41. Dinur, Irit. The PCP theorem by gap amplification. Journal of the ACM. 2007, 54 (3): 12–es. S2CID 53244523. doi:10.1145/1236457.1236459.
42. A constructive proof of the general Lovász Local Lemma. Journal of the ACM. 2010, 57 (2). ISSN 0004-5411. doi:10.1145/1667053.
43. Bulatov, Andrei A. The complexity of the counting constraint satisfaction problem. Journal of the ACM (Association for Computing Machinery (ACM)). 2013, 60 (5): 1–41. ISSN 0004-5411. S2CID 8964233. doi:10.1145/2528400.
44. Dyer, Martin; Richerby, David. An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM Journal on Computing (Society for Industrial & Applied Mathematics (SIAM)). 2013, 42 (3): 1245–1274. ISSN 0097-5397. S2CID 1247279. arXiv:1003.3879 . doi:10.1137/100811258.
45. Cai, Jin-Yi; Chen, Xi. Complexity of Counting CSP with Complex Weights. Journal of the ACM (Association for Computing Machinery (ACM)). 2017-06-22, 64 (3): 1–39. ISSN 0004-5411. S2CID 1053684. arXiv:1111.2384 . doi:10.1145/2822891.
46. Brakerski, Zvika; Vaikuntanathan, Vinod. Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. SIAM Journal on Computing. January 2014, 43 (2): 831–871. ISSN 0097-5397. doi:10.1137/120868669.
47. Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod. (Leveled) fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS '12 (New York, New York, USA: ACM Press). 2012. doi:10.1145/2090236.2090262.

參考文獻

1. The Gödel Letter. 2009-02-12 [2022-10-31]. （原始內容存檔於2019-01-30）.
2. 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. [29 March 2017]. （原始內容存檔於2019-04-16）.
3. Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 16 May 2012 [16 May 2012]. （原始內容存檔於18 July 2013）.
4. ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security 網際網路檔案館的存檔，存檔日期2013-06-01., 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 announcement 網際網路檔案館的存檔，存檔日期2017-12-09. by Association for Computing Machinery.
7. 2018 Gödel Prize citation. [2020-05-17]. （原始內容存檔於2018-10-05）.
8. 2019 Gödel Prize citation. [2020-05-17]. （原始內容存檔於2020-07-28）.
9. 2020 Gödel Prize citation. [2020-05-17]. （原始內容存檔於2020-07-16）.
10. 2021 Gödel Prize citation. [2022-10-31]. （原始內容存檔於2022-06-04）.
11. 2022 Gödel Prize citation. [2022-10-31]. （原始內容存檔於2022-10-31）.