Loading AI tools
科学奖励 来自维基百科,自由的百科全书
哥德尔奖(英语: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] |
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.