575万奖金， 2021数学界「诺奖」阿贝尔奖揭晓，以色列数学家威格森获奖，曾担任阿里达摩院十大祖师

转载：本文嚟自微信公众号“新智元”（ID:AI_era），来源：nature，编辑：小匀，转载经授权发布。

【新智元导读】昨日消息，数学界三大奖项之一「阿贝尔奖」揭晓。挪威科学同文学院将2021年阿贝尔奖授予匈牙利厄特沃什·罗兰大学教授László Lovász同美国普林斯顿高等研究院教授Avi Wigderson，佢哋是「联系数学同计算机科学嘅先驱者」。

啱啱，挪威科学同文学院公布‌年度阿贝尔奖嘅获得者是阿维·威格森（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年担任匈牙利科学院院长，喺呢啲年入面，佢为阻止匈牙利政府接管该学院嘅研究机构而做出‌大胆嘅努力，佢同第啲好多人认为，此举将降低研究人员嘅独立性。