哥德尔奖:修订间差异
外观
删除的内容 添加的内容
小 调整格式、排版 标签:2017年版源代码编辑 |
无编辑摘要 |
||
第1行: | 第1行: | ||
'''哥德尔奖'''({{lang-en|'''Gödel Prize'''}})是一個頒發給[[理論計算機科學]]領域傑出論文的年度獎項,由{{le|歐洲理論計算機科學協會|European Association for Theoretical Computer Science}}(EATCS)和[[計算機協會|美國計算機協會]]算法和計算理論特別興趣小組({{le|計算機協會算法和計算理論特別興趣小組|ACM SIGACT}})聯合頒發。該獎項是為紀念[[庫爾特·哥德爾]]而命名的。哥德爾是第一個提出[[P/NP問題]]的人,在1956年寫給[[約翰·馮·諾伊曼]]的信中,哥德爾問某個[[NP完全]]的問題是否可以用[[時間複雜度#常見時間複雜度列表|二次]]或是[[時間複雜度#線性時間|線性時間]]來解決<ref>{{Cite web | url=https://rjlipton.wordpress.com/the-gdel-letter/ | title=The Gödel Letter| date=2009-02-12}}</ref>。 |
|||
'''哥德尔奖'''({{lang-en|'''Gödel Prize'''}})由[[欧洲理论计算机学会]](EATCS)与[[美国计算机学会]]基础理论专业组织([[ACM SIGACT]])于1993年共同设立。哥德尔奖颁发给理论计算机领域最杰出的学术论文。其名称取自逻辑学与计算机科学的先驱库尔特·哥德尔(Kurt Gödel)。 |
|||
哥德爾獎於1993年開始在STOC(ACM{{le|計算理論研討會|Symposium on Theory of Computing}},北美理論計算機科學的主要會議之一)或ICALP({{le|自動機、語言和編程國際座談會|International Colloquium on Automata, Languages and Programming}},該領域的主要歐洲會議之一)上頒發。獲獎論文必須在理論計算機領域具有開創性重大貢獻,同時需在獲獎前14年內在學術期刊上正式發表。該獎項包括5,000美元的獎金<ref name="Godël2017" />。 |
|||
哥德尔被认为与亚里士多德一样是历史上最伟大的逻辑学家之一。著名的P vs. NP问题,是哥德尔在1956年写给冯·诺依曼(John von Neumann)的一封信中首次提到的。 |
|||
哥德爾獎的評審委員會由6名成員組成,分別由EATCS主席和SIGACT主席各提名三名成員,任期三年並交錯進行。委員會由EATCS和SIGACT的代表輪流擔任主席。 |
|||
哥德尔奖获奖论文必须在理论计算机领域具有开创性重大贡献;同时须在获奖前14年内在学术期刊上正式发表。 |
|||
== 获奖者 == |
|||
哥德尔奖是理论计算机领域最负盛名的奖项。评审委员会由6名成员组成,分别由EATCS主席与ACM SIGACT主席提名。评选委员会对被提名者进行严格的评审,并最终确定当年的获奖者。颁奖典礼在当年的理论计算机会议[[STOC]]或[[ICALP]]上举行。 |
|||
{| class="wikitable sortable" |
|||
!年份 !! width=40% class="unsortable"| 獲獎者 !! width=45% class="unsortable"| 原因 !!發表時間 |
|||
|-valign="top" |
|||
|1993 ||{{le|拉斯洛·鮑鮑伊|László Babai}}、[[莎菲·戈德瓦塞爾]]、[[希爾維奧·米卡利]]、{{le|什洛莫·莫蘭|Shlomo Moran}}、{{le|查爾斯·拉克福|Charles Rackoff}} || 表彰其開發[[交互式證明系統]] || 1988<ref group="paper">{{Citation | last1=Babai | first1=László | last2=Moran | first2=Shlomo | title=Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity class | url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/AMgames-Babai-Moran.pdf | year=1988 | journal=[[Journal of Computer and System Sciences]] | issn=0022-0000 | volume=36 | issue=2 | pages=254–276 | doi=10.1016/0022-0000(88)90028-1| doi-access=free }}</ref><br>1989<ref group="paper">{{Citation | last1=Goldwasser | first1=S. | last2=Micali | first2=S. | last3=Rackoff | first3=C. | title=The knowledge complexity of interactive proof systems | url=http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC02/GMR89.pdf | year=1989 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=18 | issue=1 | pages=186–208 | doi=10.1137/0218012| citeseerx=10.1.1.397.4002 }}</ref> |
|||
|-valign="top" |
|||
|1994 ||{{le|約翰·哈斯塔德|Johan Håstad}} || 表彰其證明恆深{{le|布林電路|Boolean circuit}}[[電路複雜性|大小]]的指數[[上界和下界|下界]](對於{{le|奇偶函數|Parity function}}) || 1989<ref group="paper">{{Citation | last1=Håstad | first1=Johan | series=Advances in Computing Research | volume=5 | title=Randomness and Computation | editor-first=Silvio | editor-last=Micali | chapter-url=http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf | publisher=JAI Press | year=1989 | chapter=Almost Optimal Lower Bounds for Small Depth Circuits | pages=6–20 | isbn=978-0-89232-896-3 | url-status=dead | archive-url=https://web.archive.org/web/20120222163102/http://reference.kfupm.edu.sa/content/a/l/almost_optimal_lower_bounds_for_small_de_134215.pdf | archive-date=2012-02-22 }}</ref> |
|||
|-valign=top |
|||
|1995 ||{{le|尼爾·伊莫曼|Neil Immerman}}、{{le|羅伯特·塞萊普切尼|Róbert Szelepcsényi}} || 表彰其證明非決定性空間複雜性的{{le|伊莫曼-塞萊普切尼定理|Immerman–Szelepcsényi theorem}} || 1988<ref group="paper">{{Citation | last1=Immerman | first1=Neil | author1-link=Neil Immerman | title=Nondeterministic space is closed under complementation | url=http://www.cs.umass.edu/~immerman/pub/space.pdf | year=1988 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=17 | issue=5 | pages=935–938 | doi=10.1137/0217058| citeseerx=10.1.1.54.5941 }}</ref><br>1988<ref group="paper">{{Citation | last1=Szelepcsényi | first1=R. | title=The method of forced enumeration for nondeterministic automata | year=1988 | journal=[[Acta Informatica]] | volume=26 | issue=3 | pages=279–284 | doi=10.1007/BF00299636| hdl=10338.dmlcz/120489 | s2cid=10838178 | url=http://dml.cz/bitstream/handle/10338.dmlcz/120489/ActaOstrav_03-1995-1_10.pdf }}</ref> |
|||
|-valign="top" |
|||
|1996 ||{{le|馬克·傑魯姆|Mark Jerrum}}、[[阿利斯泰爾·辛克萊爾]] || 表彰其在[[馬可夫鏈]]和矩陣[[積和式]]的近似方面的工作 || 1989<ref group="paper">{{Citation | last1=Sinclair | first1=A. | last2=Jerrum | first2=M. | title=Approximate counting, uniform generation and rapidly mixing Markov chains | year=1989 | journal=[[Information and Computation]] | issn=0890-5401 | volume=82 | issue=1 | pages=93–133 | doi=10.1016/0890-5401(89)90067-9}}</ref><br>1989<ref group="paper">{{Citation | last1=Jerrum | first1=M. | last2=Sinclair | first2=Alistair | title=Approximating the permanent | year=1989 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=18 | issue=6 | pages=1149–1178 | doi=10.1137/0218077| citeseerx=10.1.1.431.4190 }}</ref> |
|||
|-valign="top" |
|||
|1997 ||{{le|約瑟夫·哈爾彭|Joseph Halpern}}、{{le|約拉姆·莫塞斯|Yoram Moses}} || 表彰其為分佈式環境中的「知識」定義一個正式的概念 || 1990<ref group="paper">{{Citation| last1=Halpern | first1=Joseph | author-link1=Joseph Halpern| last2=Moses | first2=Yoram | author-link2=Yoram Moses| title=Knowledge and common knowledge in a distributed environment| journal=[[Journal of the ACM]]| volume=37| year=1990| pages=549–587| url=https://www.cs.cornell.edu/home/halpern/papers/common_knowledge.pdf| doi=10.1145/79147.79161| issue=3| arxiv=cs/0006009| s2cid=52151232 }}</ref> |
|||
|-valign="top" |
|||
|1998 ||{{lj|戶田誠之助|戸田 誠之助}} || 表彰其證明顯示計數解([[PP (複雜度)|PP]])和量詞交替([[PH (複雜度)|PH]])之間的關聯的[[戶田定理]] || 1991<ref group="paper">{{Citation | last1=Toda | first1=Seinosuke | title=PP is as hard as the polynomial-time hierarchy | url=http://faculty.cs.tamu.edu/chen/courses/637/2008/pres/korben.pdf | year=1991 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=20 | issue=5 | pages=865–877 | doi=10.1137/0220053| citeseerx=10.1.1.121.1246 }}</ref> |
|||
|-valign="top" |
|||
|1999 ||[[彼得·秀爾]] || 表彰其開發在[[量子計算機]]上以[[時間複雜度#多項式時間|多項式時間]]計算[[整數分解]]的[[秀爾算法]] || 1997<ref group="paper">{{Citation | last1=Shor | first1=Peter W. | title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | year=1997 | journal=[[SIAM Journal on Computing]] | issn=1095-7111 | volume=26 | issue=5 | pages=1484–1509 | doi=10.1137/S0097539795293172 | arxiv=quant-ph/9508027 | s2cid=2337707 }}</ref> |
|||
|-valign="top" |
|||
|2000 ||{{le|摩西·瓦迪|Moshe Vardi}}、{{le|皮埃爾·沃爾珀|Pierre Wolper}} || 表彰其在[[有限狀態機]]的[[時間邏輯]]方面的工作 || 1994<ref group="paper">{{Citation | last1=Vardi | first1=Moshe Y. | last2=Wolper | first2=Pierre | title=Reasoning about infinite computations | url=http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf | year=1994 | journal=Information and Computation | issn=0890-5401 | volume=115 | issue=1 | pages=1–37 | doi=10.1006/inco.1994.1092 | url-status=dead | archive-url=https://web.archive.org/web/20110825210914/http://reference.kfupm.edu.sa/content/r/e/reasoning_about_infinite_computations__102167.pdf | archive-date=2011-08-25 }}</ref> |
|||
|-valign="top" |
|||
|2001 ||{{le|桑吉夫·阿羅拉|Sanjeev Arora}}、{{le|烏列爾·費奇|Uriel Feige}}、[[莎菲·戈德瓦塞爾]]、{{le|卡斯坦·隆德|Carsten Lund}}、[[洛瓦茲·拉茲洛]]、{{le|拉耶夫·莫特瓦尼|Rajeev Motwani}}、{{le|什穆埃爾·沙夫拉|Shmuel Safra}}、{{le|邁度·蘇丹|Madhu Sudan}}、{{le|馬里奧·塞格德|Mario Szegedy}} || 表彰其證明{{le|PCP定理|PCP theorem}}以及在近似硬度方面的應用 || 1996<ref group="paper">{{Citation | last1=Feige | first1=Uriel | last2=Goldwasser | first2=Shafi | last3=Lovász | first3=Laszlo | last4=Safra | first4=Shmuel | last5=Szegedy | first5=Mario | title=Interactive proofs and the hardness of approximating cliques | url=http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf | year=1996 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=43 | issue=2 | pages=268–292 | doi=10.1145/226643.226652| doi-access=free }}</ref><br>1998<ref group="paper">{{Citation | last1=Arora | first1=Sanjeev | last2=Safra | first2=Shmuel | title=Probabilistic checking of proofs: a new characterization of NP | url=http://www.cs.umd.edu/~gasarch/pcp/AS.pdf | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=1 | pages=70–122 | doi=10.1145/273865.273901 | s2cid=751563 | url-status=dead | archive-url=https://web.archive.org/web/20110610101051/http://www.cs.umd.edu/~gasarch/pcp/AS.pdf | archive-date=2011-06-10 }} |
|||
</ref><br>1998<ref group="paper">{{Citation | last1=Arora | first1=Sanjeev | last2=Lund | first2=Carsten | last3=Motwani | first3=Rajeev | last4=Sudan | first4=Madhu | last5=Szegedy | first5=Mario | title=Proof verification and the hardness of approximation problems | url=https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=3 | pages=501–555 | doi=10.1145/278298.278306 | url-status=dead | archive-url=https://web.archive.org/web/20110610101241/https://www.cs.umd.edu/~gasarch/pcp/ALMSS.pdf | archive-date=2011-06-10 | citeseerx=10.1.1.145.4652 | s2cid=8561542 }}</ref> |
|||
|-valign="top" |
|||
|2002 ||{{le|傑霍·賽尼澤格|Géraud Sénizergues}} || 表彰其證明[[確定下推自動機]]的等價性是{{le|可決定性|Decidability (logic)|可決定}}的 || 2001<ref group="paper">{{Citation | last1=Sénizergues | first1=Géraud | title=L(A) = L(B)? decidability results from complete formal systems | year=2001 | journal=Theor. Comput. Sci. | issn=0304-3975 | volume=251 | issue=1 | pages=1–166 | doi=10.1016/S0304-3975(00)00285-1| doi-access=free }}</ref> |
|||
|-valign="top" |
|||
|2003 ||[[約阿夫·弗羅因德]]、[[羅伯特·沙皮爾]] || 表彰其開發[[機器學習]]中的[[AdaBoost]]算法 || 1997<ref group="paper">{{Citation | last1=Freund | first1=Y. | last2=Schapire | first2=R.E. | title=A decision-theoretic generalization of on-line learning and an application to boosting | url=http://www-ai.cs.tu-dortmund.de/LEHRE/PG/PG445/literatur/freund_schapire_97a.pdf | year=1997 | journal=Journal of Computer and System Sciences | issn=1090-2724 | volume=55 | issue=1 | pages=119–139 | doi=10.1006/jcss.1997.1504}}</ref> |
|||
|-valign="top" |
|||
|2004 ||{{le|莫里斯·赫利希|Maurice Herlihy}}、{{le|麥可·薩克斯 (數學家)|Michael Saks (mathematician)|麥可·薩克斯}}、{{le|尼爾·沙維特|Nir Shavit}}和{{le|弗蒂奧斯·札哈羅格羅|Fotios Zaharoglou}} || 表彰其在[[拓撲學]]在[[分佈式計算]]理論中的應用 || 1999<ref group="paper">{{Citation| last1=Herlihy | first1=Maurice | author-link1=Maurice Herlihy| last2=Shavit | first2=Nir | author-link2=Nir Shavit| title=The topological structure of asynchronous computability| journal=[[Journal of the ACM]]| volume=46| year=1999| pages=858–923| doi=10.1145/331524.331529| url=http://www.cs.brown.edu/~mph/HerlihyS99/p858-herlihy.pdf| issue=6| citeseerx=10.1.1.78.1455 | s2cid=5797174 }}. [http://www.cs.brown.edu/~mph/finland.pdf Gödel prize lecture]</ref><br>2000<ref group="paper">{{Citation| title=Wait-free ''k''-set agreement is impossible: The topology of public knowledge| last1=Saks | first1=Michael | author-link1=Michael Saks (mathematician)| last2=Zaharoglou | first2=Fotios | author-link2=Fotios Zaharoglou| journal=[[SIAM Journal on Computing]]| volume=29| year=2000| pages=1449–1483| doi=10.1137/S0097539796307698| issue=5}}</ref> |
|||
|-valign="top" |
|||
|2005 ||[[諾加·阿隆]]、{{le|約西·馬蒂亞斯|Yossi Matias}}、{{le|馬里奧·塞格德|Mario Szegedy}} || 表彰其對{{le|Streaming algorithm|串流演算法}}的基礎性貢獻 || 1999<ref group="paper">{{Citation | last1=Alon | first1=Noga | author1-link=諾加·阿隆 | last2=Matias | first2=Yossi | last3=Szegedy | first3=Mario | journal=[[Journal of Computer and System Sciences]] | url=http://www.math.tau.ac.il/~noga/PDFS/amsz4.pdf | year=1999 | title=The space complexity of approximating the frequency moments | volume=58 | issue=1 | pages=137–147 | doi=10.1006/jcss.1997.1545}}. First presented at the [[Symposium on Theory of Computing]] (STOC) in 1996.</ref> |
|||
|-valign="top" |
|||
|2006 ||{{le|曼寧德拉·阿格拉瓦爾|Manindra Agrawal}}、{{le|尼拉吉·卡亞爾|Neeraj Kayal}}、{{le|尼汀·沙克謝納|Nitin Saxena}} || 表彰其開發[[AKS質數測試]] || 2004<ref group="paper">{{Citation | last1=Agrawal | first1=M. | last2=Kayal | first2=N. | last3=Saxena | first3=N. | title=PRIMES is in P | year=2004 | journal=[[Annals of Mathematics]] | issn=0003-486X | volume=160 | pages=781–793 | doi=10.4007/annals.2004.160.781 | issue=2 | doi-access=free }}</ref> |
|||
|-valign="top" |
|||
|2007 ||{{le|亞歷山大·拉茲波洛夫|Alexander Razborov}}、{{le|史蒂芬·魯迪奇|Steven Rudich}} || 表彰其提出 {{le|自然證明|Natural proof}} || 1997<ref group="paper">{{Citation | last1=Razborov | first1=Alexander A. | last2=Rudich | first2=Steven | title=Natural proofs | id= | year=1997 | journal=[[Journal of Computer and System Sciences]] | issn=0022-0000 | volume=55 | issue=1 | pages=24–35 | doi=10.1006/jcss.1997.1494| doi-access=free }}</ref> |
|||
|-valign="top" |
|||
|2008 || {{le|丹尼爾·斯皮爾曼|Daniel Spielman}}、[[滕尚华]] || 表彰其開發算法的{{le|平滑分析|Smoothed analysis}} || 2004<ref group="paper">{{Citation | last1=Spielman | first1=Daniel A. | last2=Teng | first2=Shang-Hua | author2-link=滕尚华 | title=Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time | year=2004 | journal=J. ACM | issn=0004-5411 | volume=51 | issue=3 | pages=385–463 | doi=10.1145/990308.990310 | arxiv=math/0212413 }}</ref> |
|||
|-valign="top" |
|||
|2009 || {{le|奧馬爾·萊因戈爾德|Omer Reingold}}、{{le|薩利爾·瓦德漢|Salil Vadhan}}、[[阿維·威格森]] || 表彰其證明[[圖 (數學)|圖]]的{{le|鋸齒乘積|Zig-zag product}}和[[L (複雜度)|對數空間]]中的{{le|SL (複雜度)|SL (complexity)|無定向連接性}} || 2002<ref group="paper">{{Citation | last1=Reingold | first1=Omer | last2=Vadhan | first2=Salil | last3=Wigderson | first3=Avi | title=Entropy waves, the zig-zag graph product, and new constant-degree expanders | mr=1888797 | year=2002 | journal=[[Annals of Mathematics]] | issn=0003-486X | volume=155 | issue=1 | pages=157–187 | doi=10.2307/3062153 | jstor=3062153 | citeseerx=10.1.1.236.8669 | s2cid=120739405 }}</ref><br>2008<ref group="paper">{{Citation | last1=Reingold | first1=Omer | title=Undirected connectivity in log-space | url=http://www.weizmann.ac.il/mathusers/reingold/publications/sl.ps | year=2008 | journal=J. ACM | issn=0004-5411 | volume=55 | issue=4 | pages=1–24 | doi=10.1145/1391289.1391291 | s2cid=207168478 }}{{dead link|date=December 2017 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> |
|||
|-valign="top" |
|||
|2010 ||{{le|桑吉夫·阿羅拉|Sanjeev Arora}}、{{le|約瑟夫·S·B·米切爾|Joseph S. B. Mitchell}}|| 表彰其發現歐幾里得[[旅行推銷員問題]](ETSP)的[[多項式時間近似算法]](PTAS) || 1998<ref group="paper">{{Citation | last1=Arora | first1=Sanjeev | author1-link=Sanjeev Arora | title=Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems | doi=10.1145/290179.290180 | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=5 | pages=753–782| citeseerx=10.1.1.23.6765 | s2cid=3023351 }}</ref><BR>1999<ref group="paper">{{Citation | last1=Mitchell | first1=Joseph S. B. | author-link=Joseph S. B. Mitchell | title=Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems | doi=10.1137/S0097539796309764 | year=1999 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=28 | issue=4 | pages=1298–1309}}</ref> |
|||
|-valign="top" |
|||
|2011 || {{le|約翰·哈斯塔德|Johan Håstad}} || 表彰其證明各種組合問題的最佳非近似性結果 || 2001<ref group="paper">{{Citation | last1=Håstad | first1=Johan | author1-link=Johan Håstad | title=Some optimal inapproximability results | doi=10.1145/502090.502098 | year=2001 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=48 | issue=4 | pages=798–859 | url=http://www.nada.kth.se/~johanh/optimalinap.pdf| citeseerx=10.1.1.638.2808 | s2cid=5120748 }}</ref> |
|||
|-valign="top" |
|||
|2012 || {{le|埃利亞斯·庫特索皮亞斯|Elias Koutsoupias}}、[[赫里斯托斯·帕帕季米特里烏]]、[[諾姆·尼散]]、阿米爾·羅能(Amir Ronen)、{{le|提姆·羅加登|Tim Roughgarden}}、[[陶爾多什·埃娃]] || 表彰其奠定{{le|算法博弈論|Algorithmic game theory}}的基礎<ref name=sigact-2012>{{cite news|title=Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory|url=http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012|access-date=16 May 2012|date=16 May 2012|url-status=dead|archive-url=https://web.archive.org/web/20130718154540/http://www.acm.org/press-room/news-releases/2012/goedel-prize-2012|archive-date=18 July 2013}}</ref> || 2009<ref group=paper>{{cite journal|last=Koutsoupias|first=Elias|author2=Papadimitriou, Christos|title=Worst-case equilibria|journal=Computer Science Review|year=2009|volume=3|issue=2|pages=65–69|doi=10.1016/j.cosrev.2009.04.003}}</ref><br>2001<ref group="paper">{{cite journal|last=Nisan|first=Noam|author2=Ronen, Amir|title=Algorithmic Mechanism Design|journal=Games and Economic Behavior|year=2001|volume=35|issue=1–2|pages=166–196|doi=10.1006/game.1999.0790|citeseerx=10.1.1.21.1731}}</ref><br>2002<ref group = "paper">{{cite journal|last=Roughgarden|first=Tim|author2=Tardos, Éva|title=How bad is selfish routing?|journal=Journal of the ACM|year=2002|volume=49|issue=2|pages=236–259|doi=10.1145/506147.506153|citeseerx=10.1.1.147.1081|s2cid=207638789}}</ref> |
|||
|-valign="top" |
|||
|2013 || [[丹·博内]]、{{le|馬修·K·富蘭克林|Matthew K. Franklin}}、{{le|安托萬·朱斯|Antoine Joux}} || 表彰其開發多方[[迪菲-赫爾曼密鑰交換]]和密碼學中的{{le|博內-富蘭克林法|Boneh–Franklin scheme}}<ref>[http://www.acm.org/press-room/news-releases/2013/goedel-prize-13/ ACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security] {{webarchive|url=https://web.archive.org/web/20130601191333/http://www.acm.org/press-room/news-releases/2013/goedel-prize-13 |date=2013-06-01 }}, [[Association for Computing Machinery]], May 29, 2013.</ref> || 2003<ref group="paper">{{cite journal | last1 = Boneh | first1 = Dan | last2 = Franklin | first2 = Matthew | doi = 10.1137/S0097539701398521 | issue = 3 | journal = SIAM Journal on Computing | mr = 2001745 | pages = 586–615 | title = Identity-based encryption from the Weil pairing | volume = 32 | year = 2003| citeseerx = 10.1.1.66.1131 }}</ref><br>2004<ref group="paper">{{cite journal | last = Joux | first = Antoine | doi = 10.1007/s00145-004-0312-y | issue = 4 | journal = Journal of Cryptology | mr = 2090557 | pages = 263–276 | title = A one round protocol for tripartite Diffie-Hellman | volume = 17 | year = 2004| s2cid = 3350730 }}</ref> |
|||
|-valign="top" |
|||
|2014 || {{le|羅納德·法金|Ronald Fagin}}、阿姆農·洛特姆(Amnon Lotem)、{{le|莫尼·瑙爾|Moni Naor}} || 表彰其開發[[中介軟體]]的最佳集合算法<ref>[https://eatcs.org/index.php/component/content/article/1-news/1908-goedel-prize-2014 Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources], [[Association for Computing Machinery]], April 30, 2014.</ref> || 2003<ref group="paper">{{cite journal | last1 = Fagin | first1 = Ronald | last2 = Lotem | first2 = Amnon | last3 = Naor | first3 = Moni | doi = 10.1016/S0022-0000(03)00026-6 | issue = 4 | journal = Journal of Computer and System Sciences | pages = 614–656 | title = Optimal aggregation algorithms for middleware | volume = 66 | year = 2003| arxiv = cs/0204046 }}</ref> |
|||
|-valign="top" |
|||
|2015 || {{le|丹尼爾·斯皮爾曼|Daniel Spielman}}、[[滕尚华]] || 表彰其開發近線性時間的拉普拉斯求解器<ref>[http://www.sigact.org/Prizes/Godel/citation2015.pdf 2015 Gödel Prize announcement] {{Webarchive|url=https://web.archive.org/web/20171209021752/http://www.sigact.org/Prizes/Godel/citation2015.pdf |date=2017-12-09 }} by [[Association for Computing Machinery]].</ref> || 2011<ref group="paper" name="SpielmanTeng2011">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=Spectral Sparsification of Graphs|journal=SIAM Journal on Computing|volume=40|issue=4|year=2011|pages=981–1025|issn=0097-5397|doi=10.1137/08074489X|arxiv=0808.4134|s2cid=9646279}}</ref><br>2013<ref group="paper" name="SpielmanTeng2013">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning|journal=SIAM Journal on Computing|volume=42|issue=1|year=2013|pages=1–26|issn=0097-5397|doi=10.1137/080744888|arxiv=0809.3232|s2cid=9151077}}</ref><br>2014<ref group="paper" name="SpielmanTeng2014">{{cite journal|last1=Spielman|first1=Daniel A.|last2=Teng|first2=Shang-Hua|title=Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems|journal=SIAM Journal on Matrix Analysis and Applications|volume=35|issue=3|year=2014|pages=835–885|issn=0895-4798|doi=10.1137/090771430|arxiv=cs/0607105|s2cid=1750944}}</ref> |
|||
|- |
|||
|2016 || 史蒂芬·布魯克斯(Stephen Brookes)、{{le|彼得·歐赫恩|Peter O'Hearn}} || 表彰其開發並行{{le|分離邏輯|Separation logic}} || 2007<ref group="paper">{{cite journal|last1=Brookes|first1=Stephen|title=A Semantics for Concurrent Separation Logic|journal=Theoretical Computer Science|date=2007|volume=375|issue=1–3|pages=227–270|doi=10.1016/j.tcs.2006.12.034|url=https://www.cs.cmu.edu/~brookes/papers/seplogicrevisedfinal.pdf}}</ref><br>2007<ref group="paper">{{cite journal|last1=O'Hearn|first1=Peter|title=Resources, Concurrency and Local Reasoning|journal=Theoretical Computer Science|date=2007|volume=375|issue=1–3|pages=271–307|doi=10.1016/j.tcs.2006.12.035|url=http://www.cs.ucl.ac.uk/staff/p.ohearn/papers/concurrency.pdf|doi-access=free}}</ref> |
|||
|- |
|||
|2017<ref name=Godël2017>{{cite web|title=2017 Gödel Prize|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|website=European Association for Theoretical Computer Science|publisher=EATCS|access-date=29 March 2017}}</ref> || {{le|辛西婭·德沃克|Cynthia Dwork}}、{{le|弗蘭克·麥克謝里|Frank McSherry}}、{{le|科比·尼西姆|Kobbi Nissim}}、{{le|亞當·D·史密斯|Adam D. Smith}} || 表彰其開發[[差分隱私]] ||2006<ref group="paper">{{cite conference |title=Calibrating Noise to Sensitivity in Private Data Analysis |first1=Cynthia |last1=Dwork |first2=Frank |last2= McSherry |first3=Kobbi |last3=Nissim |first4=Adam |last4=Smith| year=2006 |conference=Theory of Cryptography (TCC)| editor1-last = Halevi| editor1-first = Shai| editor2-last=Rabin| editor2-first=Tal|series=Lecture Notes in Computer Science|volume= 3876 |publisher= Springer-Verlag |pages=265–284 |isbn=978-3-540-32731-8 |doi=10.1007/11681878_14|doi-access=free }}</ref> |
|||
|- |
|||
|2018<ref name=Godël2018>{{cite web|title=2018 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize}}</ref> || {{le|歐德德·瑞格夫 (計算機科學家)|Oded Regev (computer scientist)|歐德德·瑞格夫}} || 表彰其介紹[[容錯學習問題]] || 2009<ref group="paper" name="Regev2009">{{cite journal|last1=Regev|first1=Oded|title=On lattices, learning with errors, random linear codes, and cryptography|journal=Journal of the ACM|volume=56|issue=6|pages=1–40|doi=10.1145/1568318.1568324|year=2009|citeseerx=10.1.1.215.3543|s2cid=207156623}}</ref> |
|||
|- |
|||
|2019<ref name=Godël2019>{{cite web|title=2019 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09}}</ref> || {{le|伊里特·迪努爾|Irit Dinur}} || 表彰其利用間隙放大法重新證明{{le|PCP定理|PCP theorem}} || 2007<ref group="paper" name="Dinur2007">{{cite journal|last1=Dinur|first1=Irit|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|pages=12–es|url=https://dl.acm.org/citation.cfm?id=1236459|year=2007|doi=10.1145/1236457.1236459|s2cid=53244523}}</ref> |
|||
|- |
|||
|2020<ref name=Godël2020>{{cite web|title=2020 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16}}</ref> || 羅賓·莫瑟(Robin Moser)、{{le|陶爾多什·加博爾|Gábor Tardos}} || 表彰其對{{le|拉茲洛局部定理|Lovász local lemma}}的{{le|算法上的拉茲洛局部定理|Algorithmic Lovász local lemma|建設性證明}} || 2010<ref group="paper" name="MoserTardos2010">{{cite journal|journal=Journal of the ACM|title=A constructive proof of the general Lovász Local Lemma|volume=57|issue=2|year=2010|issn=0004-5411|doi=10.1145/1667053}}</ref> |
|||
|- |
|||
|2021<ref name=Godël2021>{{cite web|title=2021 Gödel Prize citation|url=https://eatcs.org/index.php/component/content/article/1-news/2885-2021-05-07-21-20-13}}</ref> || 安德烈·布拉托夫(Andrei Bulatov)、{{le|蔡进一|Jin-Yi Cai}}、{{le|陈汐|Xi Chen}}、{{le|馬丁·戴爾|Martin Dyer}}、大衛·里切爾比(David Richerby) || 表彰其在[[約束滿足問題]]的{{le|計數問題|Counting problem (complexity)|計數複雜性}}分類方面的工作 || 2013<ref group="paper" name="Bulatov 2013 pp. 1–41">{{cite journal | last=Bulatov | first=Andrei A. | title=The complexity of the counting constraint satisfaction problem | journal=Journal of the ACM | publisher=Association for Computing Machinery (ACM) | volume=60 | issue=5 | year=2013 | issn=0004-5411 | doi=10.1145/2528400 | pages=1–41| s2cid=8964233 }}</ref><br>2013<ref group="paper" name="Dyer Richerby 2013 pp. 1245–1274">{{cite journal | last1=Dyer | first1=Martin | last2=Richerby | first2=David | title=An Effective Dichotomy for the Counting Constraint Satisfaction Problem | journal=SIAM Journal on Computing | publisher=Society for Industrial & Applied Mathematics (SIAM) | volume=42 | issue=3 | year=2013 | issn=0097-5397 | doi=10.1137/100811258 | pages=1245–1274| arxiv=1003.3879 | s2cid=1247279 }}</ref><br>2017<ref group="paper" name="Cai Chen pp. 1–39">{{cite journal | last1=Cai | first1=Jin-Yi | last2=Chen | first2=Xi | title=Complexity of Counting CSP with Complex Weights | journal=Journal of the ACM | publisher=Association for Computing Machinery (ACM) | volume=64 | issue=3 | date=2017-06-22 | issn=0004-5411 | doi=10.1145/2822891 | pages=1–39| arxiv=1111.2384 | s2cid=1053684 }}</ref> |
|||
|- |
|||
|2022<ref>{{Cite web |title= 2022 Gödel Prize citation |url=https://eatcs.org/index.php/component/content/article/1-news/2917-2022-05-21-20-13-45}}</ref> || 茲維卡·布拉克斯基(Zvika Brakerski)、{{le|克雷格·金特里 (計算機科學家)|Craig Gentry (computer scientist)|克雷格·金特里}}、維諾德·維昆塔森(Vinod Vaikuntanathan) || 表彰其通過構建高效的全[[同態加密]](FHE)法對密碼學的變革性貢獻 || 2014<ref group="paper" name="BV11">{{Cite journal |last=Brakerski |first=Zvika |last2=Vaikuntanathan |first2=Vinod |date=January 2014 |title=Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$ |url=http://dx.doi.org/10.1137/120868669 |journal=SIAM Journal on Computing |volume=43 |issue=2 |pages=831–871 |doi=10.1137/120868669 |issn=0097-5397}}</ref><br>2014<ref group="paper" name="BGV12">{{Cite journal |last=Brakerski |first=Zvika |last2=Gentry |first2=Craig |last3=Vaikuntanathan |first3=Vinod |date=2012 |title=(Leveled) fully homomorphic encryption without bootstrapping |url=http://dx.doi.org/10.1145/2090236.2090262 |journal=Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on - ITCS '12 |location=New York, New York, USA |publisher=ACM Press |doi=10.1145/2090236.2090262}}</ref> |
|||
|} |
|||
== |
== 獲獎論文 == |
||
{{reflist|colwidth=30em|group="paper"}} |
|||
*1993年-{{tsl|en|László Babai|}},[[莎菲·戈德瓦塞尔]],[[希爾維奧·米卡利]],{{tsl|en|Shlomo Moran|}},与 {{tsl|en|Charles Rackoff|}} |
|||
*1994年-{{tsl|en|Johan Håstad|}} |
|||
*1995年-{{tsl|en|Neil Immerman|}} 与 {{tsl|en|Róbert Szelepcsényi|}} |
|||
*1996年-{{tsl|en|Mark Jerrum|}} 与[[阿利斯泰爾·辛克萊爾]] |
|||
*1997年-{{tsl|en|Joseph Halpern|}} 与 {{tsl|en|Yoram Moses|}} |
|||
*1998年-[[戶田誠之助]] |
|||
*1999年-[[彼得·秀爾]] |
|||
*2000年-[[Moshe Y. Vardi]] 与 [[Pierre Wolper]] |
|||
*2001年-[[Sanjeev Arora]],[[Uriel Feige]],[[莎菲·戈德瓦塞尔]],[[Carsten Lund]],[[László Lovász]],[[Rajeev Motwani]],[[Shmuel Safra]],[[Madhu Sudan]],与 [[Mario Szegedy]] |
|||
*2002年-[[Géraud Sénizergues]] |
|||
*2003年-[[Yoav Freund]] 与 [[Robert Schapire]] |
|||
*2004年-[[Maurice Herlihy]],[[Mike Saks]],[[Nir Shavit]] 与 [[Fotios Zaharoglou]] |
|||
*2005年-[[Noga Alon]],[[Yossi Matias]] 与 [[Mario Szegedy]] |
|||
*2006年-[[Manindra Agrawal]],[[Neeraj Kayal]],[[Nitin Saxena]] |
|||
*2007年-[[Alexander Razborov]],[[Steven Rudich]] |
|||
*2008年-[[Daniel Spielman]],[[滕尚华]] |
|||
*2009年 -[[Omer Reingold]], [[Salil Vadhan]], [[Avi Wigderson]] |
|||
*2010年 -[[Sanjeev Arora]], [[Joseph S. B. Mitchell]] |
|||
*2011年 -[[Johan Håstad]] |
|||
*2012年 -[[Elias Koutsoupias]], [[赫里斯托斯·帕帕季米特里乌]], [[Noam Nisan]], [[Amir Ronen]], [[Tim Roughgarden]]與[[愛娃·塔多斯]] |
|||
*2013年 -[[Dan Boneh]], [[Matthew K. Franklin]]與[[Antoine Joux]] |
|||
*2014年 -[[Ronald Fagin]], [[Amnon Lotem]]與[[Moni Naor]] |
|||
*2015年 -[[Daniel Spielman]],[[滕尚华]] |
|||
*2016年 -[[Stephen Brookes]],[[Peter W. O'Hearn]] |
|||
*2017年 -[[Cynthia Dwork]],[[Frank McSherry]],[[Kobbi Nissim]],[[亚当·史密斯 (计算机科学家)|亚当·史密斯]]<ref name=Godël2017>{{cite web|title=2017 Gödel Prize|url=https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|website=European Association for Theoretical Computer Science|publisher=EATCS|accessdate=29 March 2017|archive-date=2019-04-16|archive-url=https://web.archive.org/web/20190416003505/https://www.eatcs.org/index.php/component/content/article/1-news/2450-2017-godel-prize|dead-url=no}}</ref> |
|||
*2018年 -[[Oded Regev]]<ref name=Godël2018>{{cite web|title=2018 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize|accessdate=2020-05-17|archive-date=2018-10-05|archive-url=https://web.archive.org/web/20181005033058/http://eatcs.org/index.php/component/content/article/1-news/2670-2018-godel-prize|dead-url=no}}</ref> |
|||
*2019年 -[[Irit Dinur]]<ref name=Godël2019>{{cite web|title=2019 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09|accessdate=2020-05-17|archive-date=2020-07-28|archive-url=https://web.archive.org/web/20200728041139/http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09|dead-url=no}}</ref> |
|||
*2020年 -[[Robin Moser]],[[Gábor Tardos]]<ref name=Godël2020>{{cite web|title=2020 Gödel Prize citation|url=http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16|accessdate=2020-05-17|archive-date=2020-07-16|archive-url=https://web.archive.org/web/20200716154114/http://eatcs.org/index.php/component/content/article/1-news/2850-2020-03-31-12-11-16|dead-url=no}}</ref> |
|||
== 参考文献 == |
== 参考文献 == |
||
第43行: | 第80行: | ||
{{Authority control}} |
{{Authority control}} |
||
[[Category: |
[[Category:理論計算機科學]] |
||
[[Category:计算机科学奖项]] |
|||
[[Category:以人名命名的奖项]] |
[[Category:以人名命名的奖项]] |
||
[[Category:1993年建立的奖项]] |
[[Category:1993年建立的奖项]] |
||
[[Category:年度事件]] |
2022年10月31日 (一) 15:42的版本
哥德尔奖(英語:Gödel Prize)是一個頒發給理論計算機科學領域傑出論文的年度獎項,由歐洲理論計算機科學協會(EATCS)和美國計算機協會算法和計算理論特別興趣小組(計算機協會算法和計算理論特別興趣小組)聯合頒發。該獎項是為紀念庫爾特·哥德爾而命名的。哥德爾是第一個提出P/NP問題的人,在1956年寫給約翰·馮·諾伊曼的信中,哥德爾問某個NP完全的問題是否可以用二次或是線性時間來解決[1]。
哥德爾獎於1993年開始在STOC(ACM計算理論研討會,北美理論計算機科學的主要會議之一)或ICALP(自動機、語言和編程國際座談會,該領域的主要歐洲會議之一)上頒發。獲獎論文必須在理論計算機領域具有開創性重大貢獻,同時需在獲獎前14年內在學術期刊上正式發表。該獎項包括5,000美元的獎金[2]。
哥德爾獎的評審委員會由6名成員組成,分別由EATCS主席和SIGACT主席各提名三名成員,任期三年並交錯進行。委員會由EATCS和SIGACT的代表輪流擔任主席。
获奖者
獲獎論文
- ^ 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, 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)
- ^ 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, 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)
- ^ 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, 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)
- ^ 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)
- ^ 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].
- ^ Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 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.