↑ 点击蓝字关注极市平台

作者丨新智元

来源丨nature

编辑丨极市平台

极市导读

昨日消息，数学界三大奖项之一「阿贝尔奖」揭晓。挪威科学和文学院将2021年阿贝尔奖授予匈牙利厄特沃什·罗兰大学教授László Lovász和美国普林斯顿高等研究院教授Avi Wigderson，他们是「联系数学与计算机科学的先驱者」。 >>加入极市CV技术交流群，走在计算机视觉的最前沿

近日，挪威科学与文学院公布了年度阿贝尔奖的获得者是阿维·威格森（Avi Wigderson）和洛瓦兹·拉兹洛 (Lovász László），以表彰他们在「理论计算机科学和离散数学方面做出的杰出贡献，以及使其在现代数学中心领域中发挥主导作用。」

阿贝尔奖是数学界的最高荣誉之一，被称为数学界的诺贝尔奖，与菲尔兹奖齐名，前者主要吸引年轻人从事数学研究，一起扩大数学的影响是阿贝尔奖设立的主要目的。

曾获过这个奖项的数学家包括证明费马大定理的怀尔斯（Andreww J. Wiles）、电影《美丽心灵》原型约翰·纳什（John Nash），以及目前唯一一位女性获得者凯伦·乌伦贝克（Karen Keskulla Uhlenbeck）等。

曾几何时，计算机科学和纯数学几乎是完全独立的学科。如今，它们之间的距离是如此之近，以至于很难找到它们之间的界线。

Avi在计算机方面有卓越成果，而Lovász则在数学的天才，他们的研究相互交错，对理解计算中的随机性和探索高效计算的边界做出了巨大贡献。

他们在2012年的阿贝尔颁奖礼上聊天，10年后，他们将分享这一大奖

Avi Wigderson：「去随机化」的以色列计算机学家

威格森1956年出生于以色列海法。

在他十几岁的时候，计算机科学家刚刚开始勾画一个基本的理论框架——复杂性理论，涉及根据算法解决计算问题的难易程度对其进行分类。而衡量难度的主要标准是计算步骤的数量，最基本的区别是「易」与「难」。

一个简单的计算问题的例子是将两个数相乘。无论数字变得多么大，计算机都能很快找到它们的乘积。这个问题属于复杂度类「P」，它包含了所有容易解决的计算问题。

相比之下，有些计算问题则看起来很难，比如，寻找一个数的质因数（prime factor，能整除给定正整数的质数）。

目前，已知算法还没有能快速做到这一点的。但反过来就容易多了，如果你知道了某个数的质因数，只要把它们乘在一起，你就知道它们是正确的。这个问题属于「NP」，它包含的计算问题可能很难解决，但其答案很容易验证。

这也被称为「去随机化」，从这里开始，人们开始认真思考随机性也没那么重要。

20世纪70年代初，计算机科学家提出了复杂性理论的指导性猜想，问P中的问题列表是否与NP中的问题完全对应，也就是之后争论不休的：复杂度类P和NP是否是等价的（P=NP?）

这也是让威格森初露锋芒的地方。

1977年，当威格森进入以色列理工学院时，这个问题还很「时髦」。

在接下来的几十年里，他帮助阐述了将复杂性类别一一归位。

后来，威格森发表了两篇论文，在人们普遍认可的计算假设下，每个概率多项式时间算法都可以完全去随机化(derandomized)。换句话说，多项式时间计算不需要随机性，总是有可能将快速随机算法转换为快速确定性算法。

结果确定了称为BPP的复杂度类与P完全相同，也就是P = BPP，将数十年来对随机算法的研究巧妙地结合到了复杂性理论的主体中，并改变了计算机科学家看待随机算法的方式。

他还在其职业生涯早期对互联网密码学做出了贡献，包括现在用于加密货币技术的零知识证明。

当然，威格森一直活跃在学术岗位。

1983年，威格森在普林斯顿大学获得博士学位。随后，他在加州大学伯克利分校担任客座助理教授，在IBM担任访问科学家，并在伯克利的数学科学研究所(MSRI)担任研究员，1986年加入希伯来大学(Hebrew University)担任教员。自1999年以来，Wigderson一直是高等研究院数学学院的教授。Wigderson还在2009年获得哥德尔奖(Godel Prize)，获奖原因是他与Omer Reingold和Salil Vadhan合作的工作，并在1994年获得了内万林纳奖(Nevanlinna Prize)。

2018，威格森因对计算机科学和数学理论的贡献（Institute for Advanced Study）当选ACM Fellow，他还是首批坐镇阿里达摩院的十位「达摩祖师」之一。

Lovász László：数学明星、LLL算法创始人

洛瓦兹1948年出生在布达佩斯，从小就算是数学界的明星。

十几岁时，他就三块金牌加深：1964年、1965年及1966年国际数学奥林匹克竞赛金牌。22岁，洛瓦兹获得于布达佩斯罗兰大学计算机科学博士学位。

在他年轻的时候，洛瓦兹遇到了他的伯乐：匈牙利数学家Paul Erdős，后者帮助他进入了图论领域。

在当时，图论是一个数学上的「宝藏」，以提出一些有趣的问题而闻名，比如四色猜想（现在是一个已被证明的定理），在任何地图上，是否总能用四种颜色给国家上色，并且没有两个相邻的国家有相同的颜色。

洛瓦兹研究的主要影响之一是确立了离散数学能够解决计算机科学基本理论问题的方法。他说，「能够亲身经历一段数学发展与应用领域完全契合的时期，感到非常幸运。」

洛瓦兹的许多工作都集中在解决各种问题的算法的开发上。他最有影响的结果之一是LLL算法，该算法以其洛瓦兹以及Arjen和Hendrik Lenstra兄弟命名。该算法适用于被称为格的几何对象，这些几何对象是空间中的点集，其坐标通常具有整数值。

LLL算法解决了有关其属性的一个基本问题：晶格中的哪个点最接近原点？这是一个通常很难解决的简单问题，尤其是在高维空间中以及晶格中的点何时形成扭曲的形状。

目前，唯一已知能够承受量子计算机攻击的加密系统正是基于 LLL 算法。

洛瓦兹荣获过多个奖项，包括 1999 年沃尔夫奖、1999 年高德纳奖、2001 年哥德尔奖和2010年京都奖。2007年至2010年，洛瓦兹担任国际数学联盟主席。他还于2014年至2020年担任匈牙利科学院院长，在这些年里，他为阻止匈牙利政府接管该学院的研究机构而做出了大胆的努力，他和其他许多人认为，此举将降低研究人员的独立性。