2021年度阿贝尔奖揭晓：这是计算机与数学的共荣时代

海归学者发起的公益学术平台

分享信息，整合资源

交流学术，偶尔风月

在万众瞩目中，2021年阿贝尔奖由挪威自然科学与文学院授予给了匈牙利厄特沃什·罗兰大学教授László Lovász以及美国普林斯顿高等研究院教授Avi Wigderson。评委会表示，本次授奖是为了表彰他们在理论计算机科学和离散数学方面做出的杰出贡献，他们的活跃使这两个学科协同发展，并成为了现代数学的中心领域。

阿贝尔奖是由挪威设立的数学界大奖，每年颁发一次。与菲尔兹奖相比，阿贝尔奖对获奖者没有年龄限制，其奖金数额与诺贝尔奖比肩，为750万挪威克朗（约合570万人民币）。其设立初衷则是为了弥补诺奖无数学奖项的缺憾。阿贝尔奖、菲尔兹奖和沃尔夫奖并称数学三大国际奖项，在国内外学界享有广泛的影响力。阿贝尔奖设立于2001年，奖项名称是为了纪念2002年挪威著名数学家Niels Henrik Abel的200周年诞辰。2021年3月17日，Lovász和Wigderson凭借在理论计算机科学和离散数学领域的杰出成就而荣膺此奖。

从数学诞生之初，算法就一直是这个领域的核心问题。但是自从20世纪计算机问世以来，学界研究的方式与兴趣发生了根本性的转向，很多数学家已不再满足于仅仅寻找解决问题的特定算法，他们转而考虑探索算法本身的性质，以及计算的边界问题。一个可计算问题被认为是一个原则上可以用计算机解决的问题，换言之，这个问题同样可以在一系列机械的数学步骤下得到解决，例如算法。这成为了理论计算机科学的出发点之一。而离散数学和理论计算机科学的完美结合，为信息时代诸多新兴技术、理论提供了基石。

但将时间倒推至50年前，理论计算机科学和纯数学尚还是各自独立的领域。人们将很难想象，它们在不久的将来会成为枝叶相接、难以分割的交叉学科。Lovász说：“现在区分纯数学和应用数学已经越来越困难，不过我认为这是一个很好的发展趋势。” 学界公认Lovász和Wigderson在这一发展过程中发挥了核心作用，普林斯顿高等研究院的数学家Peter Sarnak表示，“计算复杂性理论和对解决问题速度的研究是在上世纪6、70年代发展起来的，而Lovász和Wigderson都是绝对的领军人物。”

László Lovász

Photo credit: Hungarian Academy of Sciences / Laszlo Mudra / Abel Prize

Lovász于1948年3月9日出生于布达佩斯，在青少年阶段便显示出了自己的数学天赋。他在高中时曾连续三年拿下国际数学奥林匹克竞赛的金牌。成为数学家后的Lovász更是荣誉无数，他于1999年获沃尔夫奖，2001年获哥德尔奖，2010年获京都奖。

Lovász研究的主要影响之一是确立了离散数学能够解决计算机科学基本理论问题的方法。他解决了离散数学多个领域中的意义重大而影响深远的问题：1972年，他解出了“完美图猜想”，该猜想是图理论中一个长期存在的开放性问题；1978年，他使用代数拓扑证明了Kneser猜想，轰动了学界；1979 年，他解决了信息理论中的经典问题，确定了五边形图的"香农容量"；Lovász 在算法设计领域最负盛名的发现是 Lovász局部引理。Lovász 还参与了一篇有关概率可检测证明定理 （PCP定理）的论文，该论文现已发展成为计算复杂性最重要的领域之一。

而除了致力于计算机科学的基础工作外，Lovász还设计了功能强大、应用广泛的算法，例如LLL算法。该算法由Lovász与Arjen Lenstra和Hendrik Lenstra一同创立，算法也因此命名为“Lenstra-Lenstra-Lovasz（LLL）”。LLL格基约化算法自1982年被提出以来，已被成功应用于计算机代数、编码理论、 密码分析、算法数论、整数规划等众多领域，显示出了非凡的发展潜力。

Avi Wigderson

Photo credit: Andrea Kane, Institute for Advanced Studies, Princeton, NJ, USA / Abel Prize

Avi Wigderson于1956年9月9日出生于以色列海法，当 他开始学术生涯时，计算复杂性理论仍处于起步阶段。他在该领域的扩大和深化过程中，作出了首屈一指的贡献。如今，计算复杂性理论这一探索算法的速度和效率的分支学科，已经发展成为数学和理论计算机科学的成熟领域。

从各种层面上而言，Wigderson都已经成为这个领域的领袖人物，他几乎对计算复杂性理论中的每一个主要开放性问题都进行了研究。不过，他的领袖地位不仅来源于他的研究范围广泛，更是因为他的领导魅力和对共同协作的热情参与。Wigderson曾与百余人共同撰写了论文，而且指导着同领域的一大批年轻科学家家。Wigderson称，“计算复杂性是一个年轻的领域。这是也一个非常民主、友好、注重合作的领域，这非常符合我的性格。当然，它充满了智力问题与挑战，不过能够生活在这个时代，我仍认为自己非常幸运。”

Wigderson深化了数学和计算机科学之间的联系，他研究了随机性在辅助计算中的作用。他以能够发现明显不相关的领域之间的联系而闻名。他与Omer Reingold 和Salil Vadhan一起发展的Zig-zag graph product就是一个示例。Zig-zag graph product将组合理论、图理论与复杂性理论相关联，并在应用方面取得了惊人的效果。Wigderson的另一个成就是对零知识证明做出了根本性的贡献，这一密码学领域的新概念，现在正被应用于区块链技术。

点击下方知社人才广场，查看最新学术招聘

扩展阅读

 

本文系网易新闻·网易号“各有态度”特色内容

媒体转载联系授权请看下方