维基百科
哥德尔奖
哥德尔奖（英語：Gödel Prize）是一個頒發給理論計算機科學領域傑出論文的年度獎項，由歐洲理論計算機科學協會（EATCS）和美國計算機協會算法和計算理論特別興趣小組（計算機協會算法和計算理論特別興趣小組）聯合頒發。該獎項是為紀念庫爾特·哥德爾而命名的。哥德爾是第一個提出P/NP問題的人，在1956年寫給約翰·馮·諾伊曼的信中，哥德爾問某個NP完全的問題是否可以用二次或是線性時間來解決[1]。
哥德爾獎於1993年開始在STOC（ACM計算理論研討會，北美理論計算機科學的主要會議之一）或ICALP（自動機、語言和編程國際座談會，該領域的主要歐洲會議之一）上頒發。獲獎論文必須在理論計算機領域具有開創性重大貢獻，同時需在獲獎前14年內在學術期刊上正式發表。該獎項包括5,000美元的獎金[2]。
哥德爾獎的評審委員會由6名成員組成，分別由EATCS主席和SIGACT主席各提名三名成員，任期三年並交錯進行。委員會由EATCS和SIGACT的代表輪流擔任主席。
获奖者
| 年份 | 獲獎者 | 原因 | 發表時間 |
|---|---|---|---|
| 1993 | 拉斯洛·鮑鮑伊、莎菲·戈德瓦塞爾、希爾維奧·米卡利、什洛莫·莫蘭、查爾斯·拉克福 | 表彰其開發交互式證明系統 | 1988[paper 1] 1989[paper 2] |
| 1994 | 約翰·哈斯塔德 | 表彰其證明恆深布林電路大小的指數下界（對於奇偶函數） | 1989[paper 3] |
| 1995 | 尼爾·伊莫曼、羅伯特·塞萊普切尼 | 表彰其證明非決定性空間複雜性的伊莫曼-塞萊普切尼定理 | 1988[paper 4] 1988[paper 5] |
| 1996 | 馬克·傑魯姆、阿利斯泰爾·辛克萊爾 | 表彰其在馬可夫鏈和矩陣積和式的近似方面的工作 | 1989[paper 6] 1989[paper 7] |
| 1997 | 約瑟夫·哈爾彭、約拉姆·莫塞斯 | 表彰其為分佈式環境中的「知識」定義一個正式的概念 | 1990[paper 8] |
| 1998 | 戶田誠之助 | 表彰其證明顯示計數解（PP）和量詞交替（PH）之間的關聯的戶田定理 | 1991[paper 9] |
| 1999 | 彼得·秀爾 | 表彰其開發在量子計算機上以多項式時間計算整數分解的秀爾算法 | 1997[paper 10] |
| 2000 | 摩西·瓦迪、皮埃爾·沃爾珀 | 表彰其在有限狀態機的時間邏輯方面的工作 | 1994[paper 11] |
| 2001 | 桑吉夫·阿羅拉、烏列爾·費奇、莎菲·戈德瓦塞爾、卡斯坦·隆德、洛瓦茲·拉茲洛、拉耶夫·莫特瓦尼、什穆埃爾·沙夫拉、邁度·蘇丹、馬里奧·塞格德 | 表彰其證明PCP定理以及在近似硬度方面的應用 | 1996[paper 12] 1998[paper 13] 1998[paper 14] |
| 2002 | 傑霍·賽尼澤格 | 表彰其證明確定下推自動機的等價性是可決定的 | 2001[paper 15] |
| 2003 | 約阿夫·弗羅因德、羅伯特·沙皮爾 | 表彰其開發機器學習中的AdaBoost算法 | 1997[paper 16] |
| 2004 | 莫里斯·赫利希、麥可·薩克斯、尼爾·沙維特、弗蒂奧斯·札哈羅格羅 | 表彰其在拓撲學在分佈式計算理論中的應用 | 1999[paper 17] 2000[paper 18] |
| 2005 | 諾加·阿隆、約西·馬蒂亞斯、馬里奧·塞格德 | 表彰其對Streaming algorithm的基礎性貢獻 | 1999[paper 19] |
| 2006 | 曼寧德拉·阿格拉瓦爾、尼拉吉·卡亞爾、尼汀·沙克謝納 | 表彰其開發AKS質數測試 | 2004[paper 20] |
| 2007 | 亞歷山大·拉茲波洛夫、史蒂芬·魯迪奇 | 表彰其提出 自然證明 | 1997[paper 21] |
| 2008 | 丹尼爾·斯皮爾曼、滕尚华 | 表彰其開發算法的平滑分析 | 2004[paper 22] |
| 2009 | 奧馬爾·萊因戈爾德、薩利爾·瓦德漢、阿維·威格森 | 表彰其證明圖的鋸齒乘積和對數空間中的無定向連接性 | 2002[paper 23] 2008[paper 24] |
| 2010 | 桑吉夫·阿羅拉、約瑟夫·S·B·米切爾 | 表彰其發現歐幾里得旅行推銷員問題（ETSP）的多項式時間近似算法（PTAS） | 1998[paper 25] 1999[paper 26] |
| 2011 | 約翰·哈斯塔德 | 表彰其證明各種組合問題的最佳非近似性結果 | 2001[paper 27] |
| 2012 | 埃利亞斯·庫特索皮亞斯、赫里斯托斯·帕帕季米特里烏、諾姆·尼散、阿米爾·羅能（Amir Ronen）、提姆·羅加登、陶爾多什·埃娃 | 表彰其奠定算法博弈論的基礎[3] | 2009[paper 28] 2001[paper 29] 2002[paper 30] |
| 2013 | 丹·博内、馬修·K·富蘭克林、安托萬·朱斯 | 表彰其開發多方迪菲-赫爾曼密鑰交換和密碼學中的博內-富蘭克林法[4] | 2003[paper 31] 2004[paper 32] |
| 2014 | 羅納德·法金、阿姆農·洛特姆（Amnon Lotem）、莫尼·瑙爾 | 表彰其開發中介軟體的最佳集合算法[5] | 2003[paper 33] |
| 2015 | 丹尼爾·斯皮爾曼、滕尚华 | 表彰其開發近線性時間的拉普拉斯求解器[6] | 2011[paper 34] 2013[paper 35] 2014[paper 36] |
| 2016 | 史蒂芬·布魯克斯（Stephen Brookes）、彼得·歐赫恩 | 表彰其開發並行分離邏輯 | 2007[paper 37] 2007[paper 38] |
| 2017[2] | 辛西婭·德沃克、弗蘭克·麥克謝里、科比·尼西姆、亞當·D·史密斯 | 表彰其開發差分隱私 | 2006[paper 39] |
| 2018[7] | 歐德德·瑞格夫 | 表彰其介紹容錯學習問題 | 2009[paper 40] |
| 2019[8] | 伊里特·迪努爾 | 表彰其利用間隙放大法重新證明PCP定理 | 2007[paper 41] |
| 2020[9] | 羅賓·莫瑟（Robin Moser）、陶爾多什·加博爾 | 表彰其對拉茲洛局部定理的建設性證明 | 2010[paper 42] |
| 2021[10] | 安德烈·布拉托夫（Andrei Bulatov）、蔡进一、陈汐、馬丁·戴爾、大衛·里切爾比（David Richerby） | 表彰其在約束滿足問題的計數複雜性分類方面的工作 | 2013[paper 43] 2013[paper 44] 2017[paper 45] |
| 2022[11] | 茲維卡·布拉克斯基（Zvika Brakerski）、克雷格·金特里、維諾德·維昆塔森（Vinod Vaikuntanathan） | 表彰其通過構建高效的全同態加密（FHE）法對密碼學的變革性貢獻 | 2014[paper 46] 2014[paper 47] |
獲獎論文
- ^ 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, ISSN 0022-0000, doi:10.1016/0022-0000(88)90028-1
- ^ Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems (PDF), SIAM Journal on Computing, 1989, 18 (1): 186–208, CiteSeerX 10.1.1.397.4002 , ISSN 1095-7111, doi:10.1137/0218012
- ^ Håstad, Johan, (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）
- ^ Immerman, Neil, Nondeterministic space is closed under complementation (PDF), SIAM Journal on Computing, 1988, 17 (5): 935–938, CiteSeerX 10.1.1.54.5941 , ISSN 1095-7111, doi:10.1137/0217058
- ^ Szelepcsényi, R., The method of forced enumeration for nondeterministic automata (PDF), Acta Informatica, 1988, 26 (3): 279–284, S2CID 10838178, doi:10.1007/BF00299636, hdl:10338.dmlcz/120489
- ^ 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
- ^ 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
- ^ Halpern, Joseph; Moses, Yoram, Knowledge and common knowledge in a distributed environment (PDF), Journal of the ACM, 1990, 37 (3): 549–587, S2CID 52151232, arXiv:cs/0006009 , doi:10.1145/79147.79161
- ^ Toda, Seinosuke, PP is as hard as the polynomial-time hierarchy (PDF), SIAM Journal on Computing, 1991, 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , ISSN 1095-7111, doi:10.1137/0220053
- ^ 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
- ^ Vardi, Moshe Y.; Wolper, Pierre, (PDF), Information and Computation, 1994, 115 (1): 1–37, ISSN 0890-5401, doi:10.1006/inco.1994.1092, （原始内容 (PDF)存档于2011-08-25）
- ^ 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, ISSN 0004-5411, doi:10.1145/226643.226652
- ^ Arora, Sanjeev; Safra, Shmuel, (PDF), Journal of the ACM, 1998, 45 (1): 70–122, ISSN 0004-5411, S2CID 751563, doi:10.1145/273865.273901, （原始内容 (PDF)存档于2011-06-10）
- ^ Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario, (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）
- ^ 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
- ^ 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, ISSN 1090-2724, doi:10.1006/jcss.1997.1504
- ^ Herlihy, Maurice; Shavit, Nir, The topological structure of asynchronous computability (PDF), Journal of the ACM, 1999, 46 (6): 858–923, CiteSeerX 10.1.1.78.1455 , S2CID 5797174, doi:10.1145/331524.331529. Gödel prize lecture
- ^ 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
- ^ 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.
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ Reingold, Omer, Undirected connectivity in log-space, J. ACM, 2008, 55 (4): 1–24, ISSN 0004-5411, S2CID 207168478, doi:10.1145/1391289.1391291[永久失效連結]
- ^ 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
- ^ 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
- ^ Håstad, Johan, Some optimal inapproximability results (PDF), Journal of the ACM, 2001, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , ISSN 0004-5411, S2CID 5120748, doi:10.1145/502090.502098
- ^ Koutsoupias, Elias; Papadimitriou, Christos. Worst-case equilibria. Computer Science Review. 2009, 3 (2): 65–69. doi:10.1016/j.cosrev.2009.04.003.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Brookes, Stephen. A Semantics for Concurrent Separation Logic (PDF). Theoretical Computer Science. 2007, 375 (1–3): 227–270. doi:10.1016/j.tcs.2006.12.034.
- ^ O'Hearn, Peter. Resources, Concurrency and Local Reasoning (PDF). Theoretical Computer Science. 2007, 375 (1–3): 271–307. doi:10.1016/j.tcs.2006.12.035 .
- ^ 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 .
- ^ 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.
- ^ Dinur, Irit. The PCP theorem by gap amplification. Journal of the ACM. 2007, 54 (3): 12–es. S2CID 53244523. doi:10.1145/1236457.1236459.
- ^ A constructive proof of the general Lovász Local Lemma. Journal of the ACM. 2010, 57 (2). ISSN 0004-5411. doi:10.1145/1667053.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
参考文献
- ^ The Gödel Letter. 2009-02-12.
- ^ 2.0 2.1 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. [29 March 2017].
- ^ . 16 May 2012 [16 May 2012]. （原始内容存档于18 July 2013）.
- ^ 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.
- ^ Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014.
- ^ 2015 Gödel Prize announcement 互联网档案馆的，存档日期2017-12-09. by Association for Computing Machinery.
- ^ 2018 Gödel Prize citation.
- ^ 2019 Gödel Prize citation.
- ^ 2020 Gödel Prize citation.
- ^ 2021 Gödel Prize citation.
- ^ 2022 Gödel Prize citation.