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

金融科技教育网

2024-04-12

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

美国计算机协会（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 还是理论计算机科学的其他多个领域的知识领袖，包括多验证人交互式证明、密码学和电路复杂性。

来源：图灵编辑部
声明：此公号（ID：Fintech_Education）发布内容和图片的目的在于传播更多信息，版权归原作者所有，不为商业用途，如有侵犯，敬请作者与我们联系

近期活动

Upcoming Activities

为了深入实践“加强金融科技人才队伍建设”和落实“金融与科技复合型人才能力培养与提升”的工作要求，中关村互联网金融研究院、中关村金融科技产业发展联盟，联合多家金融科技头部企业共同推出《金融大数据建模工程师应用能力认证项目》。3年课程研发，学制2个月，共36学时，采取线上学习，通过率92%，扫描下方二维码进行报名，随报随学。

【声明】内容源于网络

金融科技教育网

金融科技教育网主要关注如下内容：金融科技人才培养（认证课程、公开课、行业论坛、番钛客大赛、人才对接）；内容（学术前沿、创新技术）行业（金融科技、银行科技、保险科技等）；技术（人工智能、大数据、区块链、云计算、5G、物联网等）。

内容 883

粉丝 0

金融科技教育网金融科技教育网主要关注如下内容：金融科技人才培养（认证课程、公开课、行业论坛、番钛客大赛、人才对接）；内容（学术前沿、创新技术）行业（金融科技、银行科技、保险科技等）；技术（人工智能、大数据、区块链、云计算、5G、物联网等）。

总阅读233

粉丝0

内容883