阿贝尔奖和图灵奖常被称为数学界和计算机界的诺贝尔奖。此前,从未有人同时获得这两个大奖,直到现在,数学家阿维·维格森(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
联系客服