Avi Wigderson因对随机性的开创性见解获ACM A.M. Turing奖

领袖级理论计算机科学家因学科界定性贡献被嘉奖

原文：  https://amturing.acm.org/

翻译：  左    芬 

ACM, 亦即美国计算机协会（Association for Computing Machinery），今日宣布Avi Wigderson为2023年度ACM A.M. Turing奖得主，以表彰他对计算理论的奠基性贡献，包括重塑我们对计算中随机性的角色的认识，以及他对理论计算机科学中数十年的非凡引领。

Wigderson是新泽西州普林斯顿高等研究院数学院的Herbert H. Maass教授。他是多个领域的领袖级人物，包括计算复杂度理论，算法与优化，随机性与密码学，并行与分布式计算，组合学，图论，以及理论计算机科学与数学、自然科学的关联等等。

ACM A.M. Turing奖，通常被称为“计算诺贝尔奖”，会颁发由谷歌公司资助的一百万美元奖金。这一奖项以阐明计算的数学基础的英国数学家Alan M. Turing命名。

何为理论计算机科学？

理论计算机科学关注的是该学科的数学基础。它会提出这样的问题，比如“这一问题是否可以通过计算求解？”或是“如果这一问题可以计算求解，需要多少时间以及其它资源？”

理论计算机科学也探讨有效算法的设计。每一种与我们的生活息息相关的计算技术都是通过算法来实现的。理解强大而高效的算法背后的原理可以加深我们对计算机科学，甚至对自然定律的认识。尽管理论计算机科学被认为充满着激动人心的智力挑战而往往跟改善计算的实际用途不直接相关，这一科目中的研究突破已经导致了整个学科几乎所有领域的发展——从密码学、计算生物学到网络设计、机器学习以及量子计算。

为何随机性重要？

从根本上说，计算机是确定性系统；一个算法的整套指令作用在任何给定输入上都会唯一地决定它的计算过程，当然也包括它的输出。换句话说，确定性算法遵循可预测模式。与此相反，随机性缺乏定义明确的模式，或者说在事件或结果上不具有可预言性。由于我们生活的世界看上去充满着随机事件（气象系统，生物以及量子现象，等等），计算机科学家也通过在计算过程中加入随机选择来充实算法，希望以此改进它们的效率。确实，许多不存在确定性有效算法的问题已经被概率性算法有效解决，尽管伴随着一些小概率错误（可被有效缩减）。但随机性是否必不可少，或者说它是否可以去除？而要让概率性算法取得成功，所需要的随机性的品质又是什么呢？

这些连同许多其它基本问题是理解计算中的随机性与伪随机性的关键所在。对计算中随机性的动力学的深入认识可以引导我们发展更好的算法，并加深我们对计算本质的理解。

Wigderson的贡献

作为理论计算机科学研究长达四十年的领袖，Wigderson对认识计算中随机性与伪随机性的角色做出了基础的贡献。

计算机科学家们已经发现随机性与计算难度（亦即，判断自然问题有无高效算法）之间存在显著的联系。与同行一道，Wigderson撰写了一系列用难度换取随机性的影响深远的文章。他们证明，在标准的被普遍认可的计算假定下，每一个多项式时间概率型算法都可以被有效去随机化（也就是说，变成完全确定的）。换句话说，随机性对于有效计算来说不是必要的。这一系列工作革新了我们对计算中随机性角色的认知，以及我们考虑随机性的方式。这一系列雄文包含以下三篇：

“难度与随机性”（与Noam Nisan合著）。在许多其它发现之外，这篇文章引入了一种新型伪随机数生成器，并证明对随机算法的有效确定性模拟可以在比以前弱得多的前提下执行。

“BPP可次指数时间模拟，只要EXPTIME不可公开证明”（与László Babai, lance Fortnow, 以及Noam Nisan合著）。这篇文章利用“难度放大”来证明，在很弱的假定下，错误有界概率型多项式时间（BPP）对于无穷多输入长度可在次指数时间模拟。

“如果E需要指数电路则P=BPP：对XOR引理去随机化”（与Russell Impagliazzo合著）。这篇文章引入了一种更强的伪随机数生成器，从而获得本质上最优的难度与随机性互换。

尤为重要的是，Wigderson 这三篇文章的影响远远超越了随机性与去随机化领域。这些文章中的思想后来被用于理论计算机科学的多个领域，并导致了这一学科多个领袖级人物写出的重磅文章。

Wigderson仍在计算随机性这一广义领域内工作，并在与Omer Reingold, Salil Vadhan以及Michael Capalbo的共同文章中通过组合方法首次有效构建了扩张图，也就是具有强连通性质的一些稀疏图。它们在数学和理论计算机科学中都有着众多重要应用。

除了随机性的工作之外，Wigderson还是理论计算机科学的多个其它领域的卓越领袖，其中包括多方交互式证明，密码学，以及电路复杂度。

指导学生

除了技术上的开创性贡献，Wigderson还是一位受人尊敬的导师和同行，曾指导过无数的年轻研究者。他渊博的学识和无与伦比的技术熟练度——再加上他的友善，热忱，以及大度——吸引了众多优秀的年轻学子投身于理论计算机科学。

“关键的是，Avi Wigderson还获得了Abel奖，被视为数学领域终身成就最重要的荣誉，”ACM 主席Yannis Ioannidis解释。“授予他ACM A.M. Turing奖是一个恰当的跟进——因为数学是计算机科学的基石，而Wigderson的工作将众多数学子领域与理论计算机科学联系起来。理论计算机科学作为一门令人振奋的学科，吸引着最有前途的一些年轻学者去迎接最困难的挑战，而Wigderson正是这一学科中具有远见卓识的领军人物。本年度的Turing奖表彰Wigderson在随机性上的独特工作，以及他对理论计算机科学整个学科的大量间接影响。”

“Avi Wigderson在随机性以及其它主题上的工作为过去三十年里的理论计算机科学定下了基调，”谷歌的高级副总裁Jeff Dean解释道。“从计算机科学早期开始，研究者们就认识到，对于大量应用而言引入随机性有助于设计快速算法。深入理解随机性的努力一直在我们的学科获益匪浅，而Wigderson在这一领域开辟了新的疆界。谷歌也为Wigderson作为导师的贡献称颂。他的同行们赞扬他构想出了许多重大的思路和研究方向，并进而激励新一代优秀的年轻研究者们投身其中。我们祝贺Avi Wigderson获得计算界最高荣誉——ACM A.M. Turing奖。”

个人生平

（略）