2024年4月10日，美国计算机协会（ACM）宣布将2023年图灵奖（ACM A.M. Turing Award）授予普林斯顿高等研究院教授Avi Wigderson，以表彰他对计算理论的基础性贡献，包括重塑人类对计算中随机性作用的理解，以及他数十年来在理论计算机科学领域的卓越引领。

图灵奖通常被称为“计算机界的诺贝尔奖”（Nobel Prize of Computing），是计算机科学领域的最高荣誉。Wigderson曾在2021年获得数学界最高奖之一的阿贝尔奖（Abel Prize），这也使他成为同时获得数学和计算机最高奖的科学家。

ACM主席Yannis Ioannidis表示，Wigderson继获得阿贝尔奖后又获得图灵奖，是一个合适的后续奖励，因为数学是计算机科学的基础，他的工作将广泛的数学子领域与理论计算机科学联系起来。

Avi Wigderson，数学家、理论计算机科学家，普林斯顿高等研究院数学学院Herbert H. Maass教授。他在计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学、图论以及理论计算机科学与数学、科学之间的联系等领域都是领军学者，曾获得阿贝尔奖、IMU算盘奖(原名Rolf Nevanlinna奖)、高德纳奖、Edsger W. Dijkstra分布式计算奖和哥德尔奖。他是ACM会士、美国国家科学院和美国艺术与科学院院士。

40年来，作为理论计算机科学研究领域的领军学者，Wigderson为理解随机性和伪随机性在计算中的作用做出了基础性的贡献。

计算机科学家发现了随机性和计算难度(即识别无高效算法的自然问题)之间的显著联系。Wigderson与同事合作，撰写了一系列极具影响力的关于用难度换取随机性的著作。他们证明，在标准的、被广泛相信的计算假设下，每个概率多项式时间算法都可以有效地去随机化(即完全确定)。换句话说，随机性对于高效计算来说并不是必要的。这一系列著作彻底改变了人们对随机性在计算中的作用的理解，以及对随机性的思考方式。

三篇极具影响力的论文如下:

《Hardness vs. Randomness》(与Noam Nisan合著)：本文介绍了一种新型的伪随机生成器，并证明了在比以前已知的假设更弱的条件下，可以对随机算法进行高效的确定性模拟。

《BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs》(与László Babai、Lance Fortnow和Noam Nisan合著)：本文用“难度放大”（Hardness Amplification）来证明在较弱的假设条件下，有界误差概率多项式时间(BPP)可以在亚指数时间内模拟无限多的输入长度。

《P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma》(与Russell Impagliazzo合著)：本文介绍了一种更强的伪随机生成器，它在难度与随机性之间实现了基本最优的权衡。

重要的是，这三篇论文的影响远远超出了随机性和去随机化领域，这些论文中的观点被应用于理论计算机科学的许多领域，促使该领域多位领军人物发表了有影响力的论文。

Wigderson仍深耕于计算中的随机性的广阔领域，他与Omer Reingold、Salil Vadhan、Michael Capalbo合作的一篇论文中首次提出了扩展图的有效组合结构，扩展图是具有强连通性的稀疏图，在数学和理论计算机科学领域有很多重要的应用。

除了在随机性方面的研究以外，Wigderson在理论计算机科学的其他几个领域也是学术领袖，包括多验证人交互式证明、密码学和电路复杂性。

此外，他也是一位受人尊敬的导师和同事，为无数青年研究人员提供了建议。他广博的学识和无与伦比的专业性，再加上他的友善、热情和慷慨，吸引了许多极优秀的年轻人从事理论计算机科学研究。

关于图灵奖：

图灵奖是美国计算机协会于1966年设立的奖项，以英国数学家Alan M. Turing的名字命名，他阐明了计算的数学基础。该奖授予对推动信息技术产业发展有卓越贡献的计算机科学家和工程师，奖金为100万美元，由谷歌公司赞助。

学会办公室供稿，信息和图片来自图灵奖官网