史上首位阿贝尔奖、图灵奖双得主！2023图灵奖授予随机性大佬Avi Wigderson

2023 年图灵奖，刚刚揭晓！

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

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

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

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

这已不是威格德森首次斩获大奖，2019年，他就凭借在随机计算、密码学、并行计算等计算机科学基础领域做出的贡献获得高德纳奖——计算机科学界极富盛誉的奖项之一。2021年，他又与匈牙利厄特沃什·罗兰大学教授拉兹洛·洛瓦兹（LászlóLovász）一同获得国际数学界“三大奖”之一的阿贝尔奖。

在得知获图灵奖的消息后，今年67岁的威格德森在接受《自然》采访时表示“非常高兴，没想到会获奖”。他认为自己已经收获了足够多的爱和赞赏，不需要其他奖项了。

Avi Wigderson 在 UC Berkeley 的图书馆

值得一提的是，他还在5个月前来到清华叉院做客，对当下大语言模型的发展表达了自己的看法。

Wigderson的贡献

四十年来，作为理论计算机科学研究领域的领军人物，Wigderson在理解随机性和伪随机性在计算中的作用方面做出了奠基性的贡献。

计算机科学家发现了随机性与计算难度（即确定没有高效算法的自然问题）之间的显著联系。作为计算复杂性理论家，Wigderson不一定关心这些问题的答案。他常常只是想知道这些问题是否可以解决，以及如何判断。

Wigderson与同事合作，撰写了一系列极具影响力的关于用随机性换取难度的著作。他们证明，在标准的、被广泛相信的计算假设下，每一种概率多项式时间算法都可以有效地去随机化（即完全确定）。换句话说，随机性并不是高效计算的必要条件。

这一系列著作彻底改变了人们对随机性在计算中的作用的理解，也改变了人们对随机性的思考方式。

三篇影响深远的论文包括：

《Hardness vs. Randomness》（与Noam Nisan合著）：这篇论文还介绍了一种新型伪随机发生器，并证明了在比以前已知的假设更弱的条件下，可以对随机算法进行高效的确定性模拟。

论文链接：https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

《BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs》（与László Babai、Lance Fortnow、Noam Nisan合著）：本文利用  Hardness Amplification 证明，在较弱的假设条件下，有界错误概率多项式时间（BPP）可以在亚指数时间内模拟无限多的输入长度。

论文链接：https://link.springer.com/article/10.1007/BF01275486

《P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma》（与Russell Impagliazzo合著）：本文介绍了一种更强的伪随机发生器，它在难度与随机性之间实现了基本最优的权衡。

论文链接：https://dl.acm.org/doi/pdf/10.1145/258533.258590

Wigderson这三篇论文的影响远远超出了随机性和去随机化领域。这些论文中的观点随后被应用于理论计算机科学的许多领域，并激发了该领域多位领军人物发表具有影响力的论文。

目前，Wigderson与Omer Reingold、Salil Vadhan、Michael Capalbo合作，仍然在计算随机性的广泛领域开展工作，在一篇论文中首次提出了扩展图的高效组合构造（https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf）。扩展图是一种稀疏图，具有很强的连通性，在数学和理论计算机科学领域都有许多重要应用。

除了在随机性方面的研究之外，Wigderson还是理论计算机科学其他几个领域的知识领袖，包括多验证器交互式证明、密码学和电路复杂性。

图灵奖是ACM于1966年设立的奖项，专门奖励对计算机事业作出重要贡献的个人，有着「计算机界诺贝尔奖」之称，奖金为100万美元，由谷歌赞助。图灵奖的名称取自英国数学家艾伦·图灵（Alan M. Turing），他奠定了计算机的数学基础，也阐述了其局限性。

来源：机器之心pro，量子位等，爱科会易仅用于学术交流。