2023 Turing Award Announced! Princeton math professor, becomes first-ever double Abel Prize winner

Article source:NIC

[Introduction]2023年图灵奖，刚刚颁给普林斯顿数学教授Avi Wigderson！作为理论计算机科学领域的领军人物，他对于理解计算中的随机性和伪随机性的作用，做出了开创性贡献。

2023年图灵奖，刚刚揭晓！

获得这届「计算机界诺贝尔奖」——ACM A.M.图灵奖的，就是普林斯顿高等研究院数学学院的教授Avi Wigderson。

表彰的是Wigderson在计算理论领域的开创性贡献，特别是他对计算中随机性角色的重新定义，以及他在理论计算机科学领域数十年的引领。

不仅如此，这一荣誉也使Avi Wigderson成为了，历史上第一位同时获得图灵奖和阿贝尔奖的人。

阿贝尔奖被视为数学领域的最高荣誉

Wigderson是普林斯顿高级研究院数学学院的Herbert H. Maass教授。

他在计算复杂性理论、算法与优化、随机性与密码学、并行与分布式计算、组合学和图论等领域均有突出贡献，并且在理论计算机科学与数学及科学的交叉领域中，也具有重要影响。

最终，他将获得高达100万美元的奖金。

计算中的随机性和伪随机性

过去四十年里，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还在多证明者交互式证明、密码学和电路复杂度等多个理论计算机科学领域，发挥了重要的领导作用。

此外，他作为导师和同事也备受赞誉。他的亲和力、热情和慷慨，吸引了众多青年学者，投身理论计算机科学领域。

复杂性理论先驱

作为一名计算复杂性理论家，相比于问题的答案，让Avi Wigderson更感兴趣的是，这些问题是否有解决方案？以及，该如何进行判断？

「对于我们正在面对并尝试解决的每一个问题，都不能排除存在一种能够解决它的算法。这是我认为最有趣的问题。」

如今，Wigderson凭借着在计算理论基础上的杰出贡献，荣获了公认的最高荣誉之一——ACM A.M.图灵奖。

Wigderson的父亲非常热爱拼图和数学基本原理。

而在以色列海法长大的Wigderson，深受父亲的影响，

「他让我对这个领域产生了浓厚的兴趣，」Wigderson回忆道。

1970年代，Wigderson在海法大学开始了大学生涯。

最初他本主修数学，但在父母的建议下转向了计算机科学。而这背后的原因很朴素——他的父母认为，这个专业更好找工作。

虽然没去成数学专业，但Wigderson很快就发现，计算机科学是一个充满了未解之谜的领域，而这些谜题，本质上都与数学相关。

他早期的一项开创性工作，正是探讨这样一个看似矛盾的问题——

能否在不展示证明过程的情况下让人相信：一个数学命题已经得到了证明？

1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff首次提出了零知识交互证明的概念，并展示了其在若干命题上的应用。

后来，Wigderson与Micali和Oded Goldreich一起进一步阐述了这一理论，明确了这一点——

如果一个命题可以被证明，那么它也可以有一个零知识证明。

有了零知识证明，我们就可以证明自己使用密钥正确加密或签名了信息，同时不泄露任何相关的细节。

对此，普林斯顿大学的计算机科学家Ran Raz评价道：「Avi在密码学领域有许多极其重要的成果，而这，就最重要的那个。」

不过，Wigderson最最具奠基性的成就，可能在于另一个领域：将计算难度与随机性相联系。

到了1970年代末，计算机科学家们已经发现，对于许多难题，采用随机性算法（也称为概率算法）会显著优于传统的确定性算法。

例如，1977年，Robert Solovay和Volker Strassen提出了一种随机算法，可以比当时最好的确定性算法更快地判断一个数字是否为质数。

对某些问题而言，概率算法则可以引出确定性算法。

在1980年代初，Wigderson与加州大学伯克利分校的Richard Karp合作，将随机性的思想应用于那些被认为计算上极其困难的问题，也就是那些不存在已知的确定性算法能在合理时间内解决的问题。

很快，Wigderson和Karp就发现了一个难题的随机算法，并最终成功将其转化为了确定性算法。

与此同时，其他研究人也展示了，如何在密码学问题中通过计算难度的假设来实现去随机化。

由此，Wigderson也和其他人一样，开始质疑在有效解决问题时随机性的必要性，以及在什么条件下可以完全去除随机性。

随后他意识到，对随机性的需求与问题的计算难度紧密相连。

在1994年的一篇论文中，Wigderson与计算机科学家Noam Nisan共同证明——

如果真如大多数计算机科学家所猜测的那样，存在自然界中的困难问题，那么，任何高效的随机算法都可以被高效的确定性算法替代。

也就是说，随机性总是可以被消除的。

更为重要的是，他们发现确定性算法可能使用「伪随机」序列——这些数据串看起来随机，但实际上不是。

同时，他们还展示了如何利用任意难题来构建伪随机生成器。即通过将伪随机比特（不是真正的随机比特）输入到概率算法中，就可以为同一问题生成一个高效的确定性算法。

Sudan指出，这篇论文帮助计算机科学家们认识到随机性的不同程度，从而帮助揭示了难题的复杂性及其解决方法。「这其中的关键不仅仅是随机性，而是对随机性的认知，」他说。

如今，随机性已经成为复杂性理论中的一个强大工具，但它非常难以捉摸。

Wigderson指出，像硬币掷出和骰子掷出这样的行为，并不是真正的随机：如果你对这些物理系统有足够的了解，那么其结果是完全可以预测的。

但完美的随机性既难以捉摸也难以验证。

在过去几十年里，来自计算理论的发现帮助我们深入理解了许多意想不到的问题，从鸟群的集体飞行、选举结果到体内的生化反应。

最后，我们用Wigerson的一句话总结作为总结——计算的应用无处不在。

「基本上，任何自然过程都可以被视为一种演化的计算过程，因此我们可以从计算的角度来研究它。可以说，几乎所有事物都在进行某种形式的计算。」

Wigerson还曾在2009年获得了哥德尔奖。

2018年，Wigerson因对计算机科学和数学理论的贡献（Institute for Advanced Study）当选ACM Fellow。他还在2019年获得了高德纳奖。

补充知识

什么是理论计算机科学？

理论计算机科学专注于计算领域的数学基础。

它探讨的问题包括，「这个问题能否通过计算来解决？」，以及「如果这个问题可以通过计算解决，需要投入多少时间和其他资源？」

此外，理论计算机科学还致力于设计高效的算法。每一项触及我们生活的计算技术都是通过算法实现的。

深入理解构成强大和高效算法的原理，不仅能增进我们对计算机科学的认识，还能帮助我们更好地理解自然规律。

尽管理论计算机科学以其提供的激动人心的智力挑战而闻名，且通常不直接关注计算的实际应用改进，但该领域的研究成果已在从密码学、计算生物学到网络设计、机器学习及量子计算等几乎所有子领域推动了显著进展。

为什么随机性很重要？

一般来说，计算机是确定性系统——算法的指令集对任何特定输入都有唯一确定的计算过程和输出结果。

也就是说，确定性算法遵循一个可预测的模式。

然而，随机性则不同，它没有明确的模式，也无法预测事件或结果的发生。

鉴于我们所处的世界似乎充斥着随机事件（如天气系统、生物和量子现象等），计算机科学家们通过让算法在计算过程中进行随机选择，以期提高算法的效率。

事实上，许多以前没有有效的确定性算法解决方案的问题，现在通过概率算法得到了有效的解决，虽然这些算法可能会有小概率的错误（但这种错误可以有效地减少）。

但是，随机性是否是必要的，还是可以去除它？成功的概率算法需要什么样的随机性？

这些问题以及其他许多基本问题构成了理解计算中随机性和伪随机性的核心。

更深入地理解计算中随机性的动态可以帮助我们开发更优秀的算法，并深化我们对计算本质的理解。

References:

https://www.acm.org/

https://awards.acm.org/turing

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