首位图灵奖&阿贝尔奖双料获奖者：Avi Wigderson

2023 年 ACM AM 图灵奖获得者揭晓，为普林斯顿高等研究院数学学院的 Herbert H. Maass 教授 Avi Wigderson。“以表彰他对计算理论的奠基性贡献，包括重塑了我们对随机性在计算中的作用的理解，以及他数十年来在理论计算机科学领域的智力领导地位。”

Wigderson 是 ACM 院士、美国国家科学院和美国艺术与科学院院士；曾获得过的荣誉还包括：阿贝尔奖、IMU 算盘奖（以前称为 Nevanlinna 奖）、Donald E. Knuth 奖、Edsger W. Dijkstra 分布式计算奖和哥德尔奖 (Gödel Prize)。

这次获奖也使得 Wigderson 成为了历史上第一位同时获得图灵奖和阿贝尔奖的人。ACM AM 图灵奖通常被称为“计算机领域的诺贝尔奖”，奖金为 100 万美元，由谷歌提供资金支持。阿贝尔奖则被视为数学领域的最高荣誉，奖金为 80 万美元。

ACM 主席 Yannis Ioannidis 解释称：

“必须指出的是，Avi Wigderson 也曾获得阿贝尔奖，该奖被认为是数学领域终身成就最重要的荣誉。入选 ACM A.M. 图灵奖是一个合适的后续，因为数学是计算机科学的基础，而 Wigderson 的工作将广泛的数学子领域与理论计算机科学联系在一起。Wigderson 是理论计算机科学领域的一股强大的智力力量，这门令人兴奋的学科吸引了一些最有前途的年轻研究人员来攻克最艰巨的挑战。今年的图灵奖肯定了 Wigderson 在随机性方面的具体工作，以及他对整个理论计算机科学领域产生的间接但实质性的影响。”

Wigderson 在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等领域均有突出贡献，并且在理论计算机科学与数学及科学的交叉领域中，也具有重要影响。

公告称，过去四十年间，Wigderson 一直是理论计算机科学研究的领导者，为理解随机性和伪随机性在计算中的作用做出了开创性贡献。Wigderson 与同事合作撰写了一系列通过增加计算难度来减少算法中随机性需求的著作。

他们成功地证明了，在一些广泛认可的计算假设下，每个概率多项式时间算法都可以有效地去随机化（即完全确定性）。换句话说，随机性对于高效计算来说并不是必需的。这一系列作品彻底改变了大众对随机性在计算中的作用的理解，以及思考随机性的方式。

该系列有影响力的论文包括以下三篇：《Hardness vs. Randomness》、《BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proo》以及《P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma》。

重要的是，Wigderson 这三篇论文随后被应用于理论计算机科学的许多领域，并导致该领域的几位领军人物发表了有影响力的论文。除了随机性研究，Wigderson 还在多证明者交互式证明、密码学和电路复杂度等多个理论计算机科学领域充当知识领袖。