2019高德纳奖、哥德尔奖公布!阿里达摩院、以色列科学家获奖

新智元报道

来源:acm.org

编辑:肖琴

【新智元导读】今天,ACM官方公布了2019年高德纳奖和哥德尔奖的得主,分别表彰Avi Wigderson对计算随机性的革命性理解和Irit Dinur对PCP定理的基础性工作。高德纳奖和哥德尔奖是理论计算机科学界两大极富盛誉的奖项。

ACM算法与计算理论兴趣组(SIGACT)今天宣布,2019年高德纳奖授予普林斯顿大学高等研究院教授Avi Wigderson,哥德尔奖授予以色列威茨曼研究所的Irit Dinur教授。Wigderson和Dinur将在第51届计算理论年会(STOC 2019)上正式获奖。

高德纳奖(Donald E. Knuth Prize)

普林斯顿大学高等研究院Avi Wigderson教授获得2019年高德纳奖,表彰他在随机计算、密码学、电路复杂度、证明复杂度、并行计算等计算机科学基础领域做出的基础性和持久的贡献,以及对基本图形属性理解的贡献。

Avi Wigderson

在一系列研究成果中,Wigderson证明,在人们普遍认可的计算假设下,每个概率多项式时间算法都可以完全去随机化(derandomized)。换句话说,多项式时间计算不需要随机性。在密码学领域,Wigderson与人合著了两篇具有里程碑意义的论文,论证了如何在不诚实的参与者面前安全地计算任何函数。他也是一个团队的一员,这个团队展示了所有短证明问题(NP中的所有问题)实际上都有零知识证明:即证明只产生其有效性的证据,一个中心密码结构。

Wigderson于1983年在普林斯顿大学获得博士学位。随后,他在加州大学伯克利分校担任客座助理教授,在IBM担任访问科学家,并在伯克利的数学科学研究所(MSRI)担任研究员,1986年加入希伯来大学(Hebrew University)担任教员。自1999年以来,Wigderson一直是高等研究院数学学院的教授。Wigderson还在2009年获得哥德尔奖(Godel Prize),获奖原因是他与Omer Reingold和Salil Vadhan合作的工作,并在1994年获得了内万林纳奖(Nevanlinna Prize)。

Avi Wigderson还是阿里巴巴达摩院学术委员会的十位顶尖科学家之一。

高德纳奖旨在表彰个人对计算机科学基础的杰出贡献,以及他们在该领域长期的整体影响。高德纳奖的命名取自斯坦福大学的高德纳 (Donald Knuth),他被称为 “算法分析之父”。该奖项由 ACM 算法与计算理论特别兴趣组 (SIGACT) 和 IEEE 计算机学会计算数学基础技术委员会 (TCMF) 联合颁发。

哥德尔奖(Gödel Prize)

2019年哥德尔奖授予以色列威茨曼研究所的Irit Dinur教授,表彰她在“The PCP Theorem by Gap Amplification ”论文中证明了PCP定理

Irit Dinur

PCP定理是计算理论中最具影响力的结果之一,对研究近似问题的固有难度和概率证明系统研究都具有重要的意义。Dinur的论文提供了PCP定理的另一种证明,它与原来的证明有本质的不同。她的新证明比原来的证明简单得多,使其在复杂性课程中的演示成为一项可行的任务。此外,该证明显著改进了所得PCP的重要参数,对本地可测试代码产生了相同的改进,并激发了包括实际应用在内的许多研究。为如此重要的结果提供另一种证明是一项重大成就,特别是该证明解决了许多研究人员感到困惑的问题,并解决了该领域的一个中心开放问题。

Dinur在特拉维夫大学获得博士学位。之后,她先后在普林斯顿高等研究院、NEC和加州大学伯克利分校任职,之后加入以色列魏茨曼科学研究所担任计算机科学教授。Dinur还获得了Anna and Lajos Erdős Prize数学奖(2012年)和布鲁诺纪念奖(2007)。

哥德尔奖表彰对数学逻辑和计算机科学基础的重大贡献。该奖项以1906年出生在奥匈帝国(现捷克共和国)的库尔特·哥德尔(Kurt Gödel)命名。哥德尔的工作对20世纪的科学和哲学思想产生了巨大的影响。哥德尔奖由ACM SIGACT和欧洲理论计算机科学协会(EATCS)联合颁发。

原文:

https://www.acm.org/media-center/2019/june/sigact-knuth-goedel-prizes

原文发布于微信公众号 - 新智元(AI_era)

原文发表时间:2019-06-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券