2023年图灵奖揭晓：历史上首位数学和计算机最高奖得主，普林斯顿数学教授Avi Wigderson获奖...

图灵奖作为计算机科学领域的最高荣誉，通常被称为“计算界的诺贝尔奖”。

美国计算机协会（ACM） 4 月 10 日宣布，已将今年的图灵奖授予普林斯顿高等研究院计算机科学家和数学家 Avi Wigderson，因其对计算理论的基础性贡献，特别是在重塑人类对计算中随机性作用的理解以及数十年来在理论计算机科学领域的领导地位。

Avi Wigderson  将获得 100 万美元奖金。除了图灵奖外，他还是 2021 年 Abel 奖的获得者，该奖被认为是数学界的最高荣誉。他也是历史上唯一一个同时获得 Abel 奖和图灵奖的人。

“Wigderson 是理论计算机科学领域的一股高耸的智力力量，这是一门令人兴奋的学科，吸引了一些最有前途的年轻研究人员来应对最困难的挑战，”ACM 主席 Yannis Ioannidis 在一份声明中说道。“今年的图灵奖表彰了 Wigderson 在随机性方面的具体工作，以及他对整个理论计算机科学领域产生的间接但实质性的影响。

计算机算法本质上是确定性的，这使它们能够做出预测，但也限制了它们对现实世界中发现的混乱随机性的掌握。事实上，许多问题在计算上被认为是“困难的”，确定性算法很难有效地解决它们。

但是，Wigderson 和他的同事加州大学伯克利分校的计算机科学家 Richard Karp 一起找到了驯服计算难度的方法。在将随机性插入他们的算法之后，他们发现一些问题变得更容易解决了。

Wigderson 追寻这一观察，后来在其研究中证明了反向也适用：随机性总是可以从概率算法中剥离出来，将其转化为确定性算法。他的发现以独特的方式阐明了计算难度与随机性之间的联系，从而重塑了计算机科学。

“从计算机科学的早期开始，研究人员就已经认识到，结合随机性是为各种应用设计更快算法的一种方式，”谷歌研究院和谷歌 DeepMind 的首席科学家 Jeff Dean 在声明中说。“更好地理解随机性会持续为我们的领域带来重要的好处，Wigderson 在这一领域开辟了新的视野。”

为什么随机性很重要？

从根本上说，计算机是确定性系统；对于任何给定的输入，算法的指令集唯一确定了其计算，特别是其输出。换句话说，确定性算法遵循可预测的模式。相比之下，随机性则缺乏明确的模式，或者说事件或结果缺乏可预测性。

由于我们生活的世界似乎充满了随机事件（天气系统、生物和量子现象等），计算机科学家通过允许算法在计算过程中做出随机选择，借此提高算法的效率。事实上，许多没有已知高效确定性算法的问题，已经通过概率算法得到了高效解决，尽管存在一些小概率错误（可以有效减少）。

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

Wigderson的贡献

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

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

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

• “Hardness vs. Randomness”（与 Noam Nisan 合著）

  除其他发现外，该论文还介绍了一种新型伪随机发生器，并证明了在比以前所知更弱的假设下，可以对随机算法进行高效确定性模拟。
  

• “BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs”（与 László Babai、Lance Fortnow 和 Noam Nisan 合著）

  该论文利用“难度放大”证明在弱假设下可以在亚指数时间内模拟无限多输入长度的有限错误概率多项式时间（BPP）。
  

• “P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma”（与 Russell Impagliazzo 合著）

  该论文介绍一种更强的伪随机发生器，其在本质上实现了难度与随机性之间的最优权衡。

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

后来，Wigderson 与 Omer Reingold、Salil Vadhan 和 Michael Capalbo 合作，仍然在计算随机性的广泛领域开展工作，在另一篇论文中首次提出了扩展图的高效组合构造，扩展图是一种稀疏图，具有很强的连通性。它们在数学和理论计算机科学领域都有许多重要应用。

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

其他图灵奖得主作品推荐

《计算机体系结构（第6版）》

John L. Hennessy , David A. Patterson | 著

贾洪峰 | 译

本书由图灵奖得主约翰·轩尼诗和大卫·帕特森合著，堪称计算机体系结构的「圣经」，是计算机体系结构方向的学生的必读教材。

全书系统地介绍了计算机系统的设计基础、指令集系统结构、流水线与指令级并行技术、层次化存储系统与存储设备、互连网络以及多处理器系统等重要内容，讲述了使用“量化研究方法”进行计算设计，以及多种可以实现并行的技术。

《计算机程序设计艺术卷1-4A》

Donald E. Knuth | 著

李伯民，范明，蒋爱军 | 译

巫斌，范明 | 译贾洪峰 | 译

李伯民，贾洪峰 | 译 

江志强 黄志斌 | 译

图灵奖得主高德纳创作的计算机科学理论与技术的经典巨著，被《美国科学家》杂志列为二十世纪最重要的 12 本物理科学类专著之一，与爱因斯坦《相对论》、狄拉克《量子力学》、理查·费曼《量子电动力学》等经典比肩而立。

《斯坦福数据挖掘（第3版）》

Jure Leskovec, Anand Rajaraman, Jeffrey Ullman | 著

王斌 , 王达侃 | 译

当今 AI 领域最知名的学者之一 Jure Leskovec、2020 年图灵奖得主 Jeffrey Ullman 及弟子作品。

本书源自斯坦福大学公开课“CS246：海量数据挖掘”“CS224W：图机器学习”和“CS341：项目实战课”，主要关注极大规模数据的挖掘。书中包括分布式文件系统、相似性搜索、搜索引擎技术、频繁项集挖掘、聚类算法、广告管理及推荐系统、社会网络图挖掘和大规模机器学习等主要内容。

第 3 版新增了决策树、神经网络和深度学习等内容。几乎每节都有对应的习题，以此来巩固所讲解的内容。读者还可以从网上获取相关拓展资料。