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会士、美国国家科学院和美国艺术与科学院院士。

Wigderson在以色列海法长大，是一名护士和一名电气工程师的三个儿子之一，他们都是二战大屠杀的幸存者。他的父亲喜欢拼图，并对数学的基本思想非常感兴趣，他与孩子们分享了这些基本思想。“他就是让我被这种‘病毒’感染的人，”Wigderson说。1970年代，当他在海法理工学院开始上大学时，他想主修数学，但他的父母却引导他选择了计算机科学。“他们认为我毕业后能找到一份工作也许是个好主意，”他说。

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万美元，由谷歌公司赞助。

小乐数学科普：复杂性理论先驱艾维·维格森 Avi Wigderson荣获图灵奖【来自于源链接2】：

荣获2002年Rolf Nevanlinna奈望林纳奖（现称为Abacus算盘奖，参阅小乐数学科普：IMU国际数学联盟-国际数学家大会ICM 2022年获奖者揭晓（菲尔兹奖、算盘奖、陈省身奖、高斯奖、里拉瓦蒂奖） ）的哈佛大学计算机科学家Madhu Sudan（马度·苏丹）表示，Wigderson在该领域的影响不容忽视。“在计算机科学的任何领域，如果不与Avi的工作真正交叉，都是非常困难的，”苏丹说。“在任何地方，你都会发现非常深刻的见解。”例如，在1980年代末，苏丹与Wigderson合作撰写了一篇论文，研究某些数学函数和多项式之间的联系。这项工作开启了苏丹的整个职业生涯。“这对于Avi来说是典型的，”苏丹说。“他进入某个空白领域，提出正确的问题，然后继续前进。”

      他发现这个领域充满了深刻的、尚未解答的数学问题。他最早的开创性努力之一集中在一个看似矛盾的问题上：是否有可能让其他人相信一个数学命题已被证明正确而不展示如何证明它。

 普林斯顿大学计算机科学家Ran Raz（兰·拉兹）表示：“看到证明的人不会知道证明本身的任何信息。”1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff引入了零知识交互式证明（zero-knowledge interactive proof）的概念 https://dl.acm.org/doi/10.1145/22145.22178 ，演示了其在一些命题中的用途。Wigderson与Micali和Oded Goldreich后来阐述了这个想法，列出了条件，证明如果一个命题可以被证明，它也有一个零知识证明。

“这是密码学的一个关键结果；极其核心，”拉兹说。使用零知识证明，某人可以证明他们使用自己的密钥正确加密或签署了消息，而无需透露任何相关内容信息。“Avi在密码学方面有一些极其重要的成果，这可能是其中最重要的。”

      但也许Wigderson最基本的结果在于另一个领域：将计算难度与随机性联系起来。到1970年代末，计算机科学家已经意识到，对于许多难题，采用随机性的算法（也称为概率算法 probabilistic algorithm）可以远远胜过其确定性替代方案。例如，在1977年的证明 https://epubs.siam.org/doi/10.1137/0206006 中，Robert Solovay和Volker Strassen 引入了一种随机算法，可以比当时最好的确定性算法更快地确定一个数字是否为素数。

      对于某些问题，概率算法可以指向确定性算法。1980年代初，Wigderson与加州大学伯克利分校的Richard Karp（理查德·卡普）合作，将随机性的概念与计算困难的问题联系起来，这意味着没有已知的确定性算法可以在合理的时间内解决这些问题。“我们不知道如何证明它们很困难，”Wigderson说。然而，他和卡普发现了一种针对某个难题的随机算法，后来他们能够将其去随机化，从而有效地揭示了它的确定性算法。大约在同一时间，其他研究人员展示了密码学问题中的计算难度的假设如何能够实现一般的去随机化。

        随机性的不合理的有效性促使他思考随机性本身的本质。他和当时的其他研究人员一样，质疑它对于有效解决问题的必要性以及在什么条件下可以完全消除它。“最初，并不清楚这是否只因我们自己的愚蠢，而无法消除随机性，”他说。“但更大的问题是随机性是否总能有效消除。”他意识到对随机性的需求与问题的计算难度密切相关。

 在1994年的一篇论文 https://www.sciencedirect.com/science/article/pii/S0022000005800431 中，他和计算机科学家Noam Nisa阐明了这种联系。他们证明，如果存在任何自然难题，正如大多数计算机科学家所怀疑的那样，那么每一种有效的随机算法都可以被有效的确定性算法所取代。“你总是可以消除随机性，”Wigderson说。

      重要的是，他们发现确定性算法可能使用“伪随机”（pseudorandom）序列——看似随机但实际上并非随机的数据串。他们还展示了怎样使用任何难题来构建伪随机生成器。将伪随机位（而不是随机位）输入概率算法将为同一问题产生有效的确定性算法。

        苏丹表示，这篇论文帮助计算机科学家认识到随机性的程度，这有助于揭示难题的复杂性以及如何解决它们。“这不仅仅是随机性，还有对随机性的看法，”他说。“这就是关键所在。”

        苏丹指出，随机性似乎无处不在，但事实上却很难找到。“人们告诉你，圆周率的数字看起来是随机的，或者素数的数字序列看起来是随机的，”他说。“它们是完全确定的，但对我们来说它们似乎是随机的。”他说，对随机性的感知是当今计算机科学的核心。“这就是Avi大力提倡的事情。”

        随机性已成为复杂性理论中的强大资源，但它却难以捉摸。Wigderson指出，抛硬币和掷骰子并不是真正随机的：如果你有足够的关于物理系统的信息，那么结果是完全可以预测的。他说，完美的随机性是难以捉摸且难以验证的。

        但对于Wigderson来说，计算的例子无处不在——不仅在智能手机、笔记本电脑和加密算法中，而且在生物和物理系统中。近几十年来，计算理论的研究成果让人们对一系列意想不到的问题有了深入的了解，例如从鸟群和选举结果到人体内的生化反应。“基本上，任何自然过程都是一种进化，你可以将其视为计算，因此你可以这样研究它。几乎所有事情都需要计算。”

源链接：

1.https://www.csiam.org.cn/1004/202404/2076.html

2.https://mp.weixin.qq.com/s/qKH_rPnAEg16LZ9Avn_BNQ