图灵奖于2023年公布，普林斯顿数学教授，成为历史上第一位双料阿贝尔奖获奖者。

【导读】2023年图灵奖刚刚颁发给普林斯顿数学教授Avi。 Wigderson！作为理论计算机科学领域的领军人物，他在理解计算中的随机性和伪随机性方面做出了创造性的贡献。

图灵奖2023年揭晓！

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

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

最终，他获得了一百万美元的奖金。

不仅如此，这个荣誉也让Avi Wigderson已经成为历史上第一个同时拥有图灵奖和阿贝尔奖的人。

在数学领域，阿贝尔奖被认为是最高奖项

Wigderson是Herberton，一所普林斯顿高级研究所数学学院。 H. Maass教授。

他在计算复杂性理论、算法与改进、随机性与密码学、并行与分布式计算、组合与图论等方面做出了突出贡献，在理论计算机科学与数学与科学的交叉领域也产生了重要影响。

此前，Wigerson于2009年获得哥德尔奖； 2018年， 由于对计算机科学和数学理论的贡献（Institute for Advanced Study）当选ACM Fellow； 并于 获得高德纳奖的2019年。

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

在过去的40年里，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回忆道。

Wigderson于20世纪70年代在海法大学开始了他的大学生涯。

起初，他主修数学，但在父母的建议下，他转向了计算机科学。这背后的原因很简单——他的家人认为这种专业更容易找到工作。

虽然Wigderson没有成为数学专业，但是Wigderson很快发现，计算机科学是一个充满不解之谜的行业，而这些谜题本质上都与数学有关。

在他最初的开创性工作中，他正在讨论这样一个看似矛盾的问题。——

能否让人相信，一个数学命题已经被证明，而不展示证明过程？

1985年，Shafi Goldwasser、Silvio Micali和Charles Rackoff首次提出了零知识交互确认的概念，并且展示了它在几个问题上的应用。

之后，Wigderson和Micali以及Oded Goldreich共同进一步阐述了这一理论，明确了这一点。——

假如一个问题能被证明，那么它也能被证明为零知识。

通过零知识证明，我们可以在不泄露任何相关细节的情况下，证明我们正确地加密或签署了密钥。

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

然而，Wigderson最具基础的成就可能在于另一个领域：将计算难度与随机性联系起来。

在20世纪70年代末，计算机科学家发现，随机算法(也称为概率算法)在许多问题上明显优于传统的确定性算法。

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

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

20世纪80年代初，Richarderderderson和加州大学伯克利分校 Karp合作将随机思维应用于计算中极其困难的问题，即在合理的时间内无法解决的未知确定性算法的问题。

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

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

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

随后，他意识到随机需求与计算问题的难度密切相关。

Wigderson和计算机科学家Noamm在1994年的一篇论文中 Nisan证实了这一点——

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

换言之，随机性总能被消除。

更重要的是，他们发现确定性算法可能被使用。「伪随机」序列-这些信息串看起来是随机的，但实际上并非如此。

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

Sudan指出，这篇论文有助于计算机科学家认识到不同程度的随机性，从而有助于揭示问题的复杂性和解决方案。「这个问题的关键不只是随机性，而是对随机性的认识，」他说。

现在，随机性已成为复杂理论中的一种强大工具，但是它很难捉摸。

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

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

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

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

「基本上，任何自然过程都可以被视为进化的计算步骤，所以我们可以从计算的角度来研究它。可以说，几乎所有的东西都是以某种形式计算的。」

补充知识

理论计算机科学是什么？

在计算领域，理论计算机科学致力于数学基础。

其讨论的问题包括：「这一问题可以通过计算来解决吗？」，以及「若能通过计算处理这一问题，需要花费多少时间和其它资源？」

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

深入理解构成强大高效算法的原理，不仅可以提高我们对计算机科学的认识，而且可以帮助我们更好地理解自然规律。

虽然理论计算机科学以其激动人心的智商挑战而闻名，一般不直接关注计算的实际应用改进，但该领域的研究成果在大多数子领域取得了显著进展，如密码学、计算生物学、网络设计、机器学习和量子计算。

为什么随机性很重要？

一般而言，计算机是一个确定系统-算法的指令集，对于任何特定的输入都有唯一的计算步骤和输出结果。

换言之，确定性算法遵循一种可预测的方法。

但是，随机性是不同的，它没有明确的方法，也不能预测事件或结果的发生。

鉴于我们生活的世界似乎充满了随机事件(如天气系统、生物和量子现象等)。)，计算机科学家为了提高算法的效率，在计算步骤中随机抽取算法。

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

但是，随机性是必要的，还是可以消除呢？成功率算法需要什么样的随机性？

理解计算中的随机性和伪随机性是这些问题和许多其他基本问题的关键。

对计算中的随机动态有更深入的了解，可以帮助我们开发更好的算法，加深对计算本质的理解。

参考资料：

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

本文来自微信微信官方账号“新智元”（ID：AI_era），作者：新智元，36氪经授权发布。

本文仅代表作者观点，版权归原创者所有，如需转载请在文中注明来源及作者名字。

免责声明：本文系转载编辑文章，仅作分享之用。如分享内容、图片侵犯到您的版权或非授权发布，请及时与我们联系进行审核处理或删除，您可以发送材料至邮箱：service@tojoy.com