哥德爾獎(英語: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的代表輪流擔任主席。

獲獎者

More information 年份, 獲獎者 ...
年份 獲獎者 原因 發表時間
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]
Close

獲獎論文

參考文獻

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.