2023图灵奖出炉！计算机的“随机性”为何如此重要？

昨晚，美国计算机协会（ACM）宣布将 2023 年 ACM A.M. 图灵奖授予数学家和顶级理论计算机科学家 Avi Wigderson，以表彰他对计算理论的奠基性贡献，包括重塑我们对随机性在计算中的作用的理解，以及他数十年来对理论计算机科学领域的引领。

ACM A.M. 图灵奖由 ACM 于 1966 年设立，专门奖励那些对计算机事业作出重要贡献的个人。图灵奖名称取自计算机科学先驱、英国科学家 Alan M. Turing，这个奖设立目的之一正是为了纪念这位伟大的科学家。

图灵奖对获奖者要求极高，评奖程序极严，一般每年只奖励一名计算机科学家，只有极少数年度有两名在同一方向上做出贡献的科学家同时获奖。因此，图灵奖也是计算机界最负盛名、最崇高的一个奖项，有 “计算机界的诺贝尔奖” 之称。

什么是理论计算机科学？

理论计算机科学关注该领域的数学基础。它提出的问题包括：“这个问题是否可以通过计算解决？”或“如果这个问题可以通过计算解决，那么需要多少时间和其他资源？” 理论计算机科学还探索高效算法的设计。

与我们生活息息相关的每一项计算技术都是通过算法实现的。了解强大高效算法的原理，不仅能加深我们对计算机科学的理解，还能加深我们对自然规律的理解。从密码学和计算生物学到网络设计、机器学习和量子计算，理论计算机科学的研究突破几乎推动了该学科各个领域的进步。

为什么随机性很重要？

从根本上说，计算机是确定性系统；应用于任何给定输入的算法指令集唯一地决定了其计算，尤其是其输出。换句话说，确定性算法遵循的是一种可预测的模式。相比之下，随机性则缺乏明确的模式，或者说事件或结果缺乏可预测性。由于我们生活的世界中充满了天气系统、生物和量子现象等随机事件，计算机科学家丰富了算法，允许它们在计算过程中做出随机选择，借此提高算法的效率。事实上，许多没有已知高效确定性算法的问题，已经通过概率算法得到了高效解决，尽管存在一些小概率错误（可以有效减少）。

但是，随机性是必不可少的，还是可以去除？概率算法成功所需的随机性质量又如何？ 这些问题以及其他许多基本问题是理解计算中随机性和伪随机性的关键。加深对计算中随机性动态的理解，可以帮助我们开发出更好的算法，并加深我们对计算本身性质的理解。

Wigderson 的贡献

Wigderson 在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学、图论以及理论计算机科学与数学和科学之间的联系等领域，一直处于引领地位。

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

计算机科学家发现了随机性与计算难度之间的显著联系（即确定没有高效算法的自然问题）。Wigderson 与同事合作，撰写了一系列极具影响力的关于用随机性换取难度的著作。他们证明，在标准的、被广泛相信的计算假设下，每一种概率多项式时间算法都可以有效地去随机化（即完全确定）。

换句话说，随机性并不是高效计算的必要条件。这一系列著作彻底改变了我们对随机性在计算中的作用的理解，也改变了我们对随机性的思考方式。这些影响深远的论文包括以下三篇：

1）“Hardness vs. Randomness”（与 Noam Nisan 合著）。 除其他发现外，这篇论文还介绍了一种新型伪随机发生器，并证明了在比以前已知的假设更弱的条件下，随机算法的高效确定性模拟是可能的。

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

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

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

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

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

重要的是，这三篇论文的影响远远超出了随机性和反随机化领域。这些论文中的观点后来被应用于理论计算机科学的许多领域，并推动了该领域多位领军人物发表具有影响力的论文。 后来，Wigderson 与 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，仍然在计算随机性的广泛领域开展工作，在另一篇论文中首次提出了扩展图的高效组合构造，扩展图是一种稀疏图，具有很强的连通性。它们在数学和理论计算机科学领域都有许多重要应用。

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

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

受人尊敬的导师

除了开创性的技术贡献，Wigderson 还是公认的受人尊敬的导师和同事，为无数年轻研究人员提供建议。广博的知识和优秀的技术能力，加上友善、热情和慷慨，让他吸引了许多最优秀的年轻人投身于理论计算机科学领域。

“必须指出的是，Avi Wigderson 还获得了阿贝尔奖（Abel Prize），该奖项被认为是数学领域终身成就最重要的荣誉，” ACM 主席 Yannis Ioannidis 说道。 “Avi Wigderson 在随机性和其他课题方面的工作在过去三十年里为理论计算机科学制定了方向，” 谷歌高级副总裁 Jeff Dean 解释说，“从计算机科学诞生之初，研究人员就认识到，随机性是为各种应用设计更快算法的一种方法。为更好地理解随机性所做的努力将继续为我们的领域带来重要益处，Wigderson 在这一领域开辟了新天地。”

Wigderson 的履历

自 1999 年以来，Wigderson 一直担任普林斯顿高等研究院数学学院赫伯特-H-马斯教授。此前，他曾担任耶路撒冷希伯来大学教授，并在普林斯顿大学、加州大学伯克利分校、IBM 等机构担任客座教授。

Wigderson 毕业于以色列理工学院，并获得普林斯顿大学计算机科学硕士、MSE 和博士学位。他获得的荣誉包括阿贝尔奖、IMU 算盘奖、唐纳德-E-克努特奖、Edsger W. Dijkstra 分布式计算奖和哥德尔奖。他是 ACM Fellow、美国国家科学院和美国艺术与科学院院士。

参考链接：https://awards.acm.org/about/2023-turing