机器之心报道

机器之心编辑部

这位多产的研究者发现了随机性和计算之间的深刻联系，其贡献影响了密码学、复杂性等多个领域的研究。

今年的图灵奖，比往年来的要晚一些。

北京时间 4 月10日晚，计算机协会ACM宣布将2023图灵奖授予普林斯顿高等研究院数学家和顶级理论计算机科学家阿维·威格森（Avi Wigderson），以表彰他对计算理论的基础性贡献，包括塑造对计算中随机性作用的理解，以及数十年来在理论计算机科学领域的卓越领导力。

Wigderson为普林斯顿高等研究院数学学院的Herbert H. Maass教授，在计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学、图论以及理论计算机科学与数学、科学之间的关联等领域都是领军学者。

他从 20 世纪 90 年代开始在随机性和计算方面的工作揭示了数学和计算机科学之间的深刻联系，这些工作是当今研究的重要基础。

荣获 2002 年 Rolf Nevanlinna 奖（现称 Abacus 奖）的哈佛大学计算机科学家 Madhu Sudan 表示，Wigderson 在该领域的影响不容忽视。「在计算机科学的任何领域工作，如果不与 Avi 的工作真正交叉，都是非常困难的，」Sudan 表示。「在任何地方，你都会发现非常深刻的见解。」

Wigderson 在以色列海法长大，是一名护士和一名电气工程师的三个儿子之一。他的父亲喜欢拼图，并对数学的基本概念非常感兴趣，他与孩子们分享了这些想法。「我就是被他的气质所感染的人，」Wigderson表示。在 20 世纪 70 年代，当他在海法大学开始上本科时，他想主修数学，但他的父母却引导他选择了计算机科学。「他们认为我毕业后能找到一份工作也许是个好主意，」他说。

Avi Wigderson 在 UC Berkeley 的图书馆。

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

普林斯顿大学计算机科学家 Ran Raz 表示：「看到证明的人对证明本身一无所知。」1985 年，Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 引入了零知识交互式证明的概念，并演示了其在一些语句中的用途。Wigderson 与 Micali 和 Oded Goldreich 后来阐述了这个想法，列出了条件，表明如果一个陈述可以被证明，它也有一个零知识证明。

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

但也许 Wigderson 最重要的贡献在于另一个领域：将计算难度与随机性联系起来。

到 20 世纪 70 年代末，计算机科学家已经意识到，对于许多难题，采用随机性的算法（也称为概率算法）可以远远胜过其确定性替代方案。例如，在 1977 年的证明中，Robert Solovay 和 Volker Strassen 引入了一种随机算法，可以比当时最好的确定性算法更快地确定一个数字是否为素数。

对于某些问题，概率算法可以指向确定性算法。20 世纪 80 年代初，Wigderson 与加州大学伯克利分校的 Richard Karp 合作，将随机性的概念与计算困难的问题联系起来，这意味着没有已知的确定性算法可以在合理的时间内解决这些问题。

「我们不知道如何证明它们很困难，」 Wigderson说。然而，他和 Karp 发现了一种针对某个难题的随机算法，后来他们能够将其去随机化，从而有效地揭示了它的确定性算法。大约在同一时间，其他研究人员展示了密码学问题中的计算难度假设如何能够实现一般的去随机化。

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

在 1994 年的一篇论文中，他和计算机科学家 Noam Nisan 阐明了这种联系。他们证明，如果存在任何自然难题，正如大多数计算机科学家所怀疑的那样，那么每一种有效的随机算法都可以被有效的确定性算法所取代。「你总是可以消除随机性，」Wigderson 说道。

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

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

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

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

对于 Avi Wigderson 来说，可计算的例子无处不在——不仅在智能手机、笔记本电脑和加密算法中，而且在生物和物理系统中。

近几十年来，计算理论的研究成果让人们对一系列意想不到的问题有了深入的了解，从鸟类群体、选举结果到体内的生化反应。「基本上，任何自然过程都是一种进化，你可以将其视为计算，因此你可以这样研究它。几乎所有事情都需要计算，」Wigderson 说道。

此前，Wigderson 还与布达佩斯罗兰大学的数学家László Lovász共享了2021年的阿贝尔奖，该奖被誉为是数学界的诺贝尔奖。由此，他也成为了唯一一个同时摘得数学领域阿贝尔奖和计算机科学领域图灵奖的学者。

参见机器之心报道：2021 数学界 “诺奖” 阿贝尔奖揭晓，两位密码学大佬获得殊荣

今日，在接受普林斯顿高等研究院主任及Leon Levy教授David Nirenberg采访时，现年67岁的Wigderson表示自己既是数学家也是计算机科学家。

2012 年图灵奖得主、西蒙斯计算理论研究所所长、前普林斯顿高等研究院的客座教授Shafi Goldwasser表示， Wigderson对从并行算法到密码学、复杂性理论等众多领域的计算理论都做出了基础性贡献。几十年来，他在去随机化和伪随机性方面做出了大量贡献，使人们可以更深入地了解随机性在计算中的深层作用。

图灵奖是ACM于1966年设立的奖项，专门奖励对计算机事业作出重要贡献的个人，有着「计算机界诺贝尔奖」之称，奖金为100万美元，由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵（Alan M. Turing），他奠定了计算机的数学基础，也阐述了其局限性。

什么是理论计算机科学？

理论计算机科学与该领域的数学基础相关。它提出的问题包括：「这个问题是否可以通过计算解决？」或「如果这个问题可以通过计算解决，需要多少时间和其他资源？」

理论计算机科学还探索高效算法的设计。与我们生活息息相关的每一项计算技术都是通过算法实现的，了解强大高效算法的原理，不仅能加深对计算机科学的理解，还能加深对自然规律的理解。

这是一个提出「智力挑战」的领域，通常并不直接涉及改进计算的实际应用，但相关研究突破几乎推动了该领域各个领域的进步——从密码学和计算生物学到网络设计、机器学习和量子计算。

为什么随机性很重要？

从根本上来说，计算机是确定性系统。应用于任何给定输入的算法指令集唯一地决定了其计算，尤其是其输出。换句话说，确定性算法遵循可预测的模式。

相比之下，随机性缺乏明确的模式，或者说事件或结果的可预测性。由于我们生活的世界似乎充满了随机事件（天气系统、生物和量子现象等），计算机科学家通过允许算法在计算过程中做出随机选择来丰富算法，以期提高算法的效率。

而且事实上，许多尚无有效确定性算法的问题已经可以通过概率算法得到有效解决，尽管存在一些小概率误差（可以有效减少）。但随机性是必不可少的还是可以消除的？概率算法成功所需的随机性质量是多少？这些以及许多其他基本问题是理解计算中的随机性和伪随机性的核心。对计算中随机性动态的更好理解，可以使我们开发出更好的算法，并加深我们对计算本身本质的理解。

Wigderson的贡献

四十年来，作为理论计算机科学研究领域的领军人物，Wigderson在理解随机性和伪随机性在计算中的作用方面做出了奠基性的贡献。

计算机科学家发现了随机性与计算难度（即确定没有高效算法的自然问题）之间的显著联系。作为计算复杂性理论家，Wigderson不一定关心这些问题的答案。他常常只是想知道这些问题是否可以解决，以及如何判断。

Wigderson与同事合作，撰写了一系列极具影响力的关于用随机性换取难度的著作。他们证明，在标准的、被广泛相信的计算假设下，每一种概率多项式时间算法都可以有效地去随机化（即完全确定）。换句话说，随机性并不是高效计算的必要条件。

这一系列著作彻底改变了人们对随机性在计算中的作用的理解，也改变了人们对随机性的思考方式。

三篇影响深远的论文包括：

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

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

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

论文链接：https://link.springer.com/article/10.1007/BF01275486

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

论文链接：https://dl.acm.org/doi/pdf/10.1145/258533.258590

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

目前，Wigderson与Omer Reingold、Salil Vadhan、Michael Capalbo合作，仍然在计算随机性的广泛领域开展工作，在一篇论文中首次提出了扩展图的高效组合构造（https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf）。扩展图是一种稀疏图，具有很强的连通性，在数学和理论计算机科学领域都有许多重要应用。

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

受人尊敬的导师

除了突破性的技术贡献外，Wigderson还被认为是一位受人尊敬的导师和同事，为无数年轻研究人员提供了建议。他渊博的知识和无与伦比的专业性，加上他的友善、热情和慷慨，吸引了许多最优秀的年轻人从事理论计算机科学事业。

「需要指出的是，Avi Wigderson 还获得了阿贝尔奖，该奖被认为是数学领域终身成就的最重要荣誉，」ACM 主席雅尼斯·约安尼迪斯 (Yannis Ioannidis) 解释道。「被选为 ACM A.M.图灵奖得主是一个合适的后续奖励，因为数学是计算机科学的基础，而 Wigderson 的工作将广泛的数学子领域与理论计算机科学联系起来。Wigderson是理论计算机科学领域杰出的一支力量，也是一门令人兴奋的学科，吸引了一些最有前途的年轻研究人员来解决最困难的挑战。今年的图灵奖表彰了 Wigderson 在随机性方面的具体工作，以及他对整个理论计算机科学领域产生的间接但实质性的影响。」

谷歌高级副总裁 Jeff Dean 表示：「Avi Wigderson 在随机性和其他主题方面的工作为过去三十年理论计算机科学的发展设定了研究议程。」「从计算机科学的早期开始，研究人员就认识到，结合随机性是一种设计快速、广泛应用算法的好方法。更好地理解随机性为我们的领域带来重要的收益，而 Wigderson 在这一领域开辟了新的视野。谷歌也向 Wigderson 作为导师的角色致敬。他的同事们称赞他提出了伟大的想法和研究方向，然后激励了新一代年轻研究人员致力于这些研究。我们祝贺 Avi Wigderson 荣获计算机领域的最高荣誉ACM A.M.图灵奖。」

大奖拿遍的Wigderson

自 1999 年以来，Avi Wigderson一直担任新泽西州普林斯顿高等研究院数学学院Herbert H. Maass教授。此前，他曾担任耶路撒冷希伯来大学教授，并在普林斯顿大学、加州大学伯克利分校、IBM 等机构担任访问职位。

Wigderson 毕业于以色列理工学院，并获得普林斯顿大学文学硕士、工程科学硕士和计算机科学博士学位。Wigderson获得的荣誉包括阿贝尔奖、国际数学联盟算盘奖（以前称为内万林纳奖）、高德纳奖、Edsger W. Dijkstra 分布式计算奖和哥德尔奖。他是 ACM Fellow、美国国家科学院和美国艺术与科学院院士。

https://amturing.acm.org/award_winners/wigderson_3844537.cfm

https://www.quantamagazine.org/avi-wigderson-complexity-theory-pioneer-wins-turing-award-20240410/

https://www.ias.edu/news/avi-wigderson-2023-acm-am-turing-award