【新智元导读】今天，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