2021阿贝尔奖授予理论计算机科学和离散数学

发表时间:2021-05-08 12:39

拉兹洛-洛瓦兹(László Lovász,左)、艾维-维格森(Avi Wigderson)

  3月17日,2021年阿贝尔奖揭幕。挪威科学和文学院决定将2021年阿贝尔奖授予匈牙利厄特沃什-罗兰大学教授拉兹洛-洛瓦兹(László Lovász)和美国普林斯顿高等研究院教授艾维-维格森(Avi Wigderson)。“表彰他们在理论计算机科学和离散数学方面做出的杰出贡献,以及使其在现代数学中心领域中发挥主导作用。”

  “计算复杂性”理论,其本身与算法的速度和效率有关,最早于20世纪70年代提出,现已成为数学和理论计算机科学的成熟领域,为互联网安全提供了理论依据。

  同样是在20世纪70年代,新一代数学家意识到,离散数学在计算机科学中有了新的应用领域。今天,算法和互联网安全应用是我们日常生活中不可或缺的一部分。拉兹洛-洛瓦兹和艾维-维格森的研究在这一发展中发挥了重要作用。

  “在过去几十年中,拉兹洛-洛瓦兹和艾维-维格森一直是推动实现相关发展的主导力量。他们的研究在很多方面是相互交错的,特别是,他们都对理解计算中的随机性和探索高效计算的边界做出了巨大贡献,”阿贝尔奖委员会主席汉斯-考斯(Hans Munthe-Kaas)表示。

  他说:“正是由于这两位所做出的突破性贡献,离散数学和相对“年轻”的理论计算机科学领域现已牢固确立为现代数学的中心领域。”

  阿贝尔奖于2002年1月1日设立,于2003年6月3日首次颁发,其目的是颁发给数学领域杰出科学工作者,奖金为750万挪威克朗。阿贝尔奖与菲尔兹奖、沃尔夫奖,被称为国际最高数学“三大奖”。华人数学家丘成桐是菲尔兹奖首位华人得主、沃尔夫数学奖得主;陶哲轩获得菲尔兹奖,陈省身获得沃尔夫数学奖。

  人物小传:

  拉兹洛-洛瓦兹(László Lovász)

  拉兹洛-洛瓦兹在十几岁时,就成为了一位数学界的明星,且已跻身过去半个世纪以来最杰出的数学家之列。他的研究为离散数学和计算机科学领域之间搭建了联系。

  他于1948 年出生于匈牙利布达佩斯,他在布达佩斯一所专为天才学生教授专业数学课的高中学习,Katalin Vesztergombi是他的同班同学是,后来两人成为夫妻。拉兹洛·洛瓦兹学业出色,曾荣获1964年、1965年及1966年国际数学奥林匹克竞赛金牌。后就读于布达佩斯罗兰大学,22岁获得计算机科学博士学位。

  他曾以作家的身份为社区服务,作品以清晰易懂而著称。同时,他也是一名鼓舞人心的讲师和一名出色的领导者,还曾担任过一届国际数学联盟主席(2007-2010年)。

  在他青少年时代,最重要的机遇是他遇到了他心中的数学英雄、匈牙利著名的数学家保罗-厄尔多斯(Paul Erd s),保罗-厄尔多斯鼓励拉兹洛-洛瓦兹从事“匈牙利式组合数学”研究,主要关注图的属性。这不仅确立了拉兹洛-洛瓦兹最初的研究方向,也为他后来“共享与协作”的数学研究风格铺平了道路。

  20世纪70年代,图理论成为最早能够阐明新兴计算复杂性领域的纯数学领域之一。拉兹洛-洛瓦兹研究的主要影响之一是确立了离散数学能够解决计算机科学基本理论问题的方法。他说,“能够亲身经历一段数学发展与应用领域完全契合的时期,感到非常幸运。”

  除了在计算机科学基础方面的研究外,拉兹洛-洛瓦兹还设计了具有广泛应用的强大算法。LLL算法即为其中之一,该算法以拉兹洛-洛瓦兹与阿仁-伦斯特拉(Arjen-Lenstra)和亨德里克-伦斯特拉(Hendrik-Lenstra)兄弟的名字命名,它代表了在理解格基(一种基础的几何对象)方面的概念性突破,在数字理论、密码学和移动计算等领域有着卓越的应用。目前,唯一已知能够承受量子计算机攻击的加密系统正是基于 LLL 算法。

  拉兹洛-洛瓦兹荣获过多个奖项,包括 1999 年沃尔夫奖、1999 年高德纳奖、2001 年哥德尔奖和2010年京都奖。

  艾维-维格森(Avi Wigderson)

  艾维-维格森于1956年出生于以色列海法。毕业于以色列理工学院学习,获得计算机科学理学士学位,后转到普林斯顿大学攻读研究生,1983年凭借论文《组合复杂性的研究》获得博士学位,后在耶路撒冷的希伯来大学任教,并被授予终身教职。

  1999年,艾维-维格森加入普林斯顿高等研究院 (IAS),并工作至今。2016年,在庆祝艾维-维格森60岁生日时,普林斯顿高等研究院院长罗贝特-捷格拉夫(Robbert Dijkgraaf)说,艾维-维格森开创了理论计算机科学领域在该研究院的黄金时代。

  20世纪70年代末,当艾维-维格森开始他的学术生涯时,“计算复杂性”理论仍处于起步阶段。可以说,他对扩大和深化该领域的贡献卓著,使得该学科现已成为数学和理论计算机科学的成熟领域,使得计算复杂性变得非常重要——为互联网安全提供了理论依据。

  互联网密码学是复杂性理论目前最重要的应用。艾维-维格森在他职业生涯早期对此做出了根本性的贡献,包括现在用于加密货币技术的零知识证明。

  艾维-维格森对复杂性理论中的每一个主要的开放性问题都进行了研究,也由于他平易近人的人格魅力和对热衷于与他人合作研究,他与100多人共同撰写了论文,并指导了一大批年轻的复杂性理论家。

  “能够生活在这个时代,我认为自己非常幸运。”他说。“计算复杂性是一个年轻的领域,也一个非常民主、非常友好、非常注重合作的领域,非常符合我的天性。当然,它充满了智力问题与挑战。”

  艾维-维格森在以色列理工学院求学时结识了他现在的夫人埃德娜(Edna),埃德娜目前也在高等研究院计算机系工作,他们已有3个孩子和两个孙子。

  1994年,艾维-维格森获得了罗尔夫-内万林纳计算机科学奖、2009年哥德尔奖和2019年高德纳奖等。