2023图灵奖揭晓：计算理论奠基人Avi Wigderson得奖

络绎科学 · 公众号 · · 2024-04-11 23:32

正文

美国计算机协会（ACM）在北京时间 4 月 10 日晚宣布，数学家与理论计算机科学家阿维·维格德森（ Avi Wigderson ）凭借对计算中“随机性”原理的深刻洞察与杰出贡献，荣获了备受瞩目的图灵奖。

美国计算机协会设立的图灵奖，旨在表彰在计算机科学领域做出杰出贡献的先驱者，其地位与诺贝尔奖相当，备受瞩目。该奖项每年颁发，获奖者名单星光熠熠，其中包括万维网创始人蒂姆·伯纳斯-李（ Tim Berners-Lee ）以及被誉为“人工智能之父”的杰弗里·辛顿（ Geoffrey Hinton ），他的工作对人工神经网络的理解产生了深远影响。Avi Wigderson 教授加入这一行列，无疑是对他卓越成就的最高认可。

在普林斯顿高等研究院， Avi Wigderson 领导着计算机科学和离散数学（CSDM）项目，该项目于 1999 年正式成立，当时他成为研究院的终身教职人员。不过，研究院作为计算研究领域的领先中心的历史要远早于此。由研究院创始人之一约翰·冯·诺依曼领导的电子计算机项目（ECP），成功研制出了世界上第一台存储程序计算机，并安置于研究院校园内。ECP 项目所生产的这台计算机，正是图灵所提出的计算数学基础的实际应用。而 Avi Wigderson 在研究院继续传承了这一传统，ACM 颁发图灵奖就是认可了他对计算机科学理论基础的诸多贡献。

Avi Wigderson 在以色列的海法长大，出身于一个电气工程师和护士家庭，是家中三个孩子之一。他的父母都是大屠杀的幸存者。他的父亲对数学的基本理念有着浓厚的兴趣，并热衷于解谜，经常与孩子们分享这些乐趣。“可以说，我就是从他那里‘感染’上了对数学的热爱。”Avi Wigderson 说。上世纪 70 年代，他进入海法的以色列理工学院求学，原本打算主修数学，但在父母的建议下，他选择了计算机科学。“他们认为，选择这个专业能让我在毕业后更容易找到一份稳定的工作。”Avi Wigderson 回忆道。

然而，即使是学计算机， Avi Wigderson 还是选择了与数学联系更加密切的理论计算机科学。他于 1977 年进入以色列理工学院（Technion），并于 1980 年获得计算机科学学士学位。随后，他前往普林斯顿大学深造，并于 1983 年获得博士学位，其博士论文为《组合复杂度的研究》，导师是理查德·利普顿。1986 年，Avi Wigderson 回到以色列，在耶路撒冷的希伯来大学任职。次年，他获得终身教职，并于 1991 年成为全职教授。随后在 1999 年，Avi Wigderson 加入普林斯顿高等研究院，并一直留任至今。

在其科研生涯的四十多年里， Avi Wigderson 一直致力于研究各种问题。但作为计算复杂性理论专家，他并不怎么关心这些问题的答案。他通常只想知道这些问题是否可解，以及如何判断。Avi Wigderson 觉得这种情况很不可思议，因为无论一个问题看起来多么困难，都有可能存在着一个解决它的有效方法，只是这个方法可能刚好超出了我们的触及范围。他曾经说过：“就我所知，对于我们试图解决的每一个问题，都不能排除有一个能够解决它们的算法存在。这是我最感兴趣的问题。”

Avi Wigderson 早期最具突破性的研究聚焦于一个看似矛盾的问题：如何在不透露证明过程的情况下，说服别人某个数学命题已经得到了证明。他认为看到证明的人并不会了解到证明本身的任何内容。早在 1985 年，沙菲·戈德瓦塞尔、西尔维奥·米卡利和查尔斯·拉克奥夫便提出了零知识交互式证明的概念，并展示了它在某些命题中的应用。随后，Avi Wigderson 与米卡利和奥德·戈德赖希共同深化了这一理念，他们阐明，如果一个命题能够被证明，那么它就一定存在一种零知识证明的方式。

这是密码学领域的一个关键成果。使用零知识证明，人们可以确认所使用的密钥已经正确地对消息进行了加密或签名，而不会在这个过程中透露任何关于密钥的信息。 Avi Wigderson 在密码学领域取得了一些非常重要的成果，而这可能是其中最重要的一项。

而 Avi Wigderson 更大的贡献则是帮助我们理解随机性与伪随机性在计算中的作用。计算机科学的研究很早就发现了随机性与计算复杂度间的一种显著关联，即存在某些天然难题，它们缺乏有效的解决算法。在 20 世纪 70 年代，计算机理论家提出了关于计算性质的一些基本思想，尤其是 P 和 NP 的概念。P 是指计算机能够轻松解决的问题的集合，比如在几秒内就能解决的问题；而 NP 包含计算机难以解决的问题，这意味着已知的方法可能需要数百万年才能找到答案。所有这些困难问题能否简化为容易解决的问题，即 P 是否等于 NP，是计算复杂性的基本问题。事实上，这现在被认为是整个数学领域中最重要的未解问题之一。

Avi Wigderson 通过研究随机性在计算中的作用，在这一领域取得了重大突破。有些难题可以通过算法来简化，在算法中，计算机会在计算过程中抛硬币。然而，如果算法依赖于随机性，那么总有可能出现错误，导致解决方案出错。

1994 年， Avi Wigderson 和诺姆·尼桑撰写了一篇开创性的论文。他们在论文中主张，相比以往所知的条件，我们现在可以在更宽松的假设下，实现随机算法的高效确定性模拟。在这项研究中，他们发现确定性算法可以使用“伪随机”序列——即看起来是随机的但实际上不是的数据串。他们还展示了如何利用任何困难问题来构建一个伪随机数生成器。将伪随机位（而不是随机位）输入到概率算法中，将针对同一问题得到一个高效的确定性算法。在随后的研究中，Avi Wigderson 和同事们基于公认的常规计算假设，证明了所有概率多项式时间算法均能被有效转化为完全确定的形式，实现去随机化。换言之，高效计算并不依赖于随机性。

这颠覆了计算机科学家对随机性的认知方式，其思想广泛应用于理论计算机科学诸多领域，并影响了后来的算法设计。“从并行算法到密码学到复杂性理论的所有层面， Avi Wigderson 都为计算理论做出了根本性的贡献，”西蒙斯计算理论研究所所长、普林斯顿高等研究院前访问教授（2021 年）、2012 年图灵奖得主 Shafi Goldwasser 表示，“他数十年来在去随机化和伪随机性领域的众多贡献，使我们对随机性在计算中所起的深刻作用有了深入理解。”

对此， Avi Wigderson 曾表示，尽管他的研究主要聚焦于数学领域，但其目标是理解计算科学中的概念。这种跨学科的研究方法使他在两个领域都赢得了极高的声誉，被公认为多才多艺的学者。

普林斯顿大学计算机科学教授兰·拉兹对 Avi Wigderson 的评价极高，他表示：“Avi Wigderson 是理论计算机科学领域的核心人物。我曾在耶路撒冷的希伯来大学作为他的研究生，深受其影响。”

2023图灵奖揭晓：计算理论奠基人Avi Wigderson得奖

正文

请到「今天看啥」查看全文