哥德尔奖（）是一個頒發給理論計算機科學領域傑出論文的年度獎項，由（EATCS）和美國計算機協會算法和計算理論特別興趣小組（）聯合頒發。該獎項是為紀念庫爾特·哥德爾而命名的。哥德爾是第一個提出P/NP問題的人，在1956年寫給約翰·馮·諾伊曼的信中，哥德爾問某個NP完全的問題是否可以用二次或是線性時間來解決。
哥德爾獎於1993年開始在STOC（ACM，北美理論計算機科學的主要會議之一）或ICALP（，該領域的主要歐洲會議之一）上頒發。獲獎論文必須在理論計算機領域具有開創性重大貢獻，同時需在獲獎前14年內在學術期刊上正式發表。該獎項包括5,000美元的獎金
1989
|-valign="top"
|1994 || || 表彰其證明恆深大小的指數下界（對於） || 1989
|-valign=top
|1995 ||、 || 表彰其證明非決定性空間複雜性的 || 1988
1988
|-valign="top"
|1996 ||、阿利斯泰爾·辛克萊爾 || 表彰其在馬可夫鏈和矩陣積和式的近似方面的工作 || 1989
1989
|-valign="top"
|1997 ||、 || 表彰其為分佈式環境中的「知識」定義一個正式的概念 || 1990
|-valign="top"
|1998 || || 表彰其證明顯示計數解（PP）和量詞交替（PH）之間的關聯的戶田定理 || 1991
|-valign="top"
|1999 ||彼得·秀爾 || 表彰其開發在量子計算機上以多項式時間計算整數分解的秀爾算法 || 1997
|-valign="top"
|2000 ||、 || 表彰其在有限狀態機的時間邏輯方面的工作 || 1994
|-valign="top"
|2001 ||、、莎菲·戈德瓦塞爾、、洛瓦茲·拉茲洛、、、、 || 表彰其證明以及在近似硬度方面的應用 || 1996
1998
1998
|-valign="top"
|2002 || || 表彰其證明確定下推自動機的等價性是的 || 2001
|-valign="top"
|2003 ||約阿夫·弗羅因德、羅伯特·沙皮爾 || 表彰其開發機器學習中的AdaBoost算法 || 1997
|-valign="top"
|2004 ||、、、 || 表彰其在拓撲學在分佈式計算理論中的應用 || 1999
2000
|-valign="top"
|2005 ||諾加·阿隆、、 || 表彰其對的基礎性貢獻 || 1999
|-valign="top"
|2006 ||、、 || 表彰其開發AKS質數測試 || 2004
|-valign="top"
|2007 ||、 || 表彰其提出 || 1997
|-valign="top"
|2008 || 、滕尚华 || 表彰其開發算法的 || 2004
|-valign="top"
|2009 || 、、阿維·威格森 || 表彰其證明圖的和對數空間中的 || 2002
2008
|-valign="top"
|2010 ||、|| 表彰其發現歐幾里得旅行推銷員問題（ETSP）的多項式時間近似算法（PTAS） || 19981999
|-valign="top"
|2011 || || 表彰其證明各種組合問題的最佳非近似性結果 || 2001
|-valign="top"
|2012 || 、赫里斯托斯·帕帕季米特里烏、諾姆·尼散、、、陶爾多什·埃娃 || 表彰其奠定的基礎|| 2009
2001
2002
|-valign="top"
|2013 || 丹·博内、、 || 表彰其開發多方迪菲-赫爾曼密鑰交換和密碼學中的|| 2003
2004
|-valign="top"
|2014 || 、阿姆農·洛特姆（Amnon Lotem）、 || 表彰其開發中介軟體的最佳集合算法|| 2003
|-valign="top"
|2015 || 、滕尚华 || 表彰其開發近線性時間的拉普拉斯求解器|| 2011
2013
2014
|-
|2016 || 史蒂芬·布魯克斯（Stephen Brookes）、 || 表彰其開發並行 || 2007
2007
|-
|2017|| 、、、 || 表彰其開發差分隱私 ||2006
|-
|2018|| || 表彰其介紹容錯學習問題 || 2009
|-
|2019|| || 表彰其利用間隙放大法重新證明 || 2007
|-
|2020|| 羅賓·莫瑟（Robin Moser）、 || 表彰其對的 || 2010
|-
|2021|| 安德烈·布拉托夫（Andrei Bulatov）、、、、大衛·里切爾比（David Richerby） || 表彰其在約束滿足問題的{{le|分類方面的工作 || 2013
2013
2017
|-
|2022|| 茲維卡·布拉克斯基（Zvika Brakerski）、、維諾德·維昆塔森（Vinod Vaikuntanathan） || 表彰其通過構建高效的全同態加密（FHE）法對密碼學的變革性貢獻 || 2014
2014
|-
|2023
|塞繆爾·費奧里尼（Samuel Fiorini）、、塞巴斯蒂安·波庫塔（Sebastian Pokutta）、漢斯·拉吉·提瓦利（Hans Raj Tiwary）、、托馬斯·羅斯沃斯（Thomas Rothvoss）
|表彰其透過建構高效率的完全同態加密（FHE）方案，對密碼學所做的轉變性貢獻
|2015,2017
|-
|2024
|
|表彰他在電路下界和「下界演算法」範例方面的工作
|2011
|-
|2025
|艾尚·查托帕迪亞伊（Eshan Chattopadhyay）、
|以表彰其建構「具備多對數最小熵的顯式雙源萃取器，解決了計算理論中一個已存在將近三十年的核心問題」
|2016
|}
獲獎論文
参考文献
评论 (0)