连接数学和计算机科学的先驱

阿贝尔奖和图灵奖常被称为数学界和计算机界的诺贝尔奖。此前，从未有人同时获得这两个大奖，直到现在，数学家阿维·维格森（Avi Wigderson）成为了史上首个荣获这两个奖项的科学家。

4月10日，美国计算机学会（ACM）宣布将2023年图灵奖授予维格森，以表彰他对计算理论的基础性贡献。维格森的工作几乎触及了这一学科的每一个领域。他的同事、合作者和学员都说，他总是能在不同的领域之间发现意想不到的桥梁。从20世纪90年代开始，他对随机性和计算所展开的研究工作，就为数学和计算机科学之间建立了深刻的联系。

1956年，维格森出生在以色列海法。他是计算复杂性理论、算法和优化、随机性和密码学、并行和分布式计算、组合学、图论等领域的先驱。除了刚刚荣获的图灵奖，他还与洛瓦茲·拉茲洛 （Lovász László）在2021年一同荣获了数学领域的最高奖——阿贝尔奖。（图/Peter Badge）

随机性与确定性

从本质上说，计算机是确定性系统。确定性算法遵循的是可预测的模式。相比之下，随机性缺乏明确的模式，或者说缺乏对事件或结果的可预测性。

在20世纪70年代末，许多计算机科学家已经意识到，对于许多难题，采用随机性的算法，即概率算法，远胜于确定性算法。许多没有有效确定性算法的问题，都可以被概率算法有效地解决，尽管存在一些小的出错率。‍‍‍‍

随机性的令人惊讶的有效性，引发计算机科学家思考随机性本身的本质，他们开始质疑随机性对于有效解决问题有多必要，以及在什么情况下它是可以被完全移除的。

这些问题，以及许多其他相关的基本问题，是理解计算中随机和伪随机的核心。更好地理解计算中的随机动态，有助于科学家发展出更好的算法，并加深对计算的本质的理解。

维格森的贡献

维格森在计算机科学的各个领域都作出了广泛而深刻的贡献，而他将随机性与困难问题联系起来的工作，可能是其中最为显著的成就。

维格森与合作者发表了一系列极具影响力的论文。在20世纪90年代发表的两篇论文中，他与合作者证明了在特定的假设下，对于高效计算来说，随机性并不是必需的。

他们提出了一个有点类似于P≠NP的猜想，P=BPP，这个等式意味着每个随机算法都可以被去随机化，并转化为具有可观效率的确定性算法；此外，去随机化是通用且普遍的，它不依赖于随机化算法的内部细节。

另一种看待这个问题的方式是将其视为难度和随机性之间的权衡：如果存在一个足够困难的问题，那么随机性就可以通过高效的确定性算法进行模拟。维格森随后证明了与之相反的观点，他得出的结论认为：即使是针对具有已知随机算法的特定问题的有效确定性算法，也意味着一定存在这样一个困难问题。‍‍

这一工作与伪随机（看起来随机）的对象紧密相关。维格森的工作构建了伪随机生成器，它将几个真正随机的比特变成许多伪随机比特，从一个不完美的随机源中提取出近乎完美的随机比特。

维格森的这些工作的影响，远远超出了随机和去随机领域。他的这些想法随后被应用于理论计算机科学的众多领域。‍

维格森并没有止步于此，他仍致力于研究计算随机性的广泛领域。在另一组论文中，他给出了扩展图（具有强连通性的稀疏图）的第一个有效的组合结构，这些扩展图在数学和理论计算机科学中都有许多重要应用。

‍‍‍

指导与传承

除了在学术上做出了突破性的贡献外，维格森还被公认为一位受人尊敬的导师和同事，他为无数年轻的研究人员无私地提供建议。他渊博的知识和无与伦比的技术，加上他的友好、热情和慷慨，吸引了许多最优秀的年轻人从事理论计算机科学的研究。

#创作团队：

编译：佐佑

排版：雯雯

#参考来源：

https://amturing.acm.org/

https://www.abelprize.no

#图片来源：

封面图&首图：Entre_Humos/pixabay