2023年图灵奖揭晓！普林斯顿数学教授，成史上首位阿贝尔奖双料获奖者

文章来源：新智元

【导读】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的这三篇论文，其理论被广泛应用于理论计算机科学的多个分支，并且激发了多位专家的重要研究。