哥德爾獎

哥德爾獎（英語：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]
2023[12]	塞繆爾·費奧里尼（Samuel Fiorini）、塞爾日·馬薩爾（英語：Serge Massar）、塞巴斯蒂安·波庫塔（Sebastian Pokutta）、漢斯·拉吉·提瓦利（Hans Raj Tiwary）、隆納·德·沃爾夫（英語：Ronald de Wolf）、托馬斯·羅斯沃斯（Thomas Rothvoss）	表彰其透過建構高效率的完全同態加密（FHE）方案，對密碼學所做的轉變性貢獻	2015,[paper 48]2017[paper 49]
2024[13]	萊恩·威廉斯（英語：Ryan Williams (computer scientist)）	表彰他在電路下界和「下界演算法」範例方面的工作	2011[paper 50]
2025[14]	艾尚·查托帕迪亞伊（Eshan Chattopadhyay）、大衛·祖克曼（英語：David Zuckerman (computer scientist)）	以表彰其建構「具備多對數最小熵的顯式雙源萃取器，解決了計算理論中一個已存在將近三十年的核心問題」	2016[paper 51]