曾被“纯”数学家看不起的研究,摘得数学界“诺贝尔奖”

从互联网安全到网络研究的种种应用都离不开两位得奖者的工作

本文来自微信公众号:Nature Portfolio(ID:nature-portfolio),作者:Davide Castelvecchi,原文标题:《曾被“纯”数学家看不起的研究摘得2021年阿贝尔奖》,头图来自:Andrea Kane/Institute for Advanced Study, left; Laszlo Mudra/Hungarian Academy of Sciences

计算理论领域的两名先驱获得了2021年阿贝尔奖。阿贝尔奖是数学界的最高荣誉之一。

当地时间3月17日,挪威科学与文学院宣布2021年阿贝尔奖被授予匈牙利数学家László Lovász和以色列计算机科学家Avi Wigderson,以表彰“他们在理论计算科学和离散数学作出的奠基性贡献,以及将这两个领域发展为现代数学核心方面的引领作用”。两人将分享750万挪威克朗(约合580万人民币)的奖金。

László Lovász(左)和Avi Wigderson共同获得2021年阿贝尔奖。来源:(左)Hungarian Academy of Sciences/Laszlo Mudra/AbelPrize;(右)Cliff Moore/Institute for Advanced Study, Princeton/AbelPrize

目前就职于美国普林斯顿高等研究院(IAS)的Wigderson告诉《自然》,这次获奖的是整个计算理论,而不仅仅是他本人的工作。他说:“我觉得这对整个领域都极其重要。”

目前就职于匈牙利罗兰大学的Lovász说:“今天,想要分辨纯数学和应用数学越来越难了——我觉得这是个好的发展。”

算法从古希腊开始就是数学的核心,小学生在校学的简单长除法也属于算法。但是从20世纪计算机诞生以来,算法研究的侧重点就从“有算法能解决这个问题吗?”变成了“有算法能在真正的计算机上用合理的时间解决这个问题吗?至少是从理论上?”

Lovász和Wigderson在这些算法的发展中起到了关键作用,普林斯顿高等研究院的数论学家Peter Sarnak说:“算法的复杂性理论以及对解决问题速度的研究分别是在上世纪60年代和70年代确立的,而这两位绝对属于开宗立派的人物。”

从数学到计算

Lovász于1948年出生在布达佩斯,他的成长环境鼓励超常儿童参加难度很大的解题比赛。他的早期灵感大多来源于Paul Erdős——现代历史上最多产的数学家。Erdős的工作主要是关于离散物体(例如网络中的节点)及其关系的数学,而非几何学等领域中常见的连续变量,Alfréd Rényi数学研究所的数学家Péter Pál Pálfy说。

Lovász的职业生涯刚起步时,曾经被“纯”数学家看不起的网络理论等离散数学领域正变得重要起来——无论是对数学的其他领域还是对“大数据”分析等应用都变得日益重要。他对于基础研究及其应用都很感兴趣。在入职学术界前,他曾在微软做了7年的全职研究员。他解决了数学网络理论的一些重要问题,例如在保证相邻节点是不同颜色的前提下,有多少种给节点涂色的可能方法[1]

Lovász最著名的成果之一是他与荷兰数论学家Arjen Lenstra和Hendrik Lenstra两兄弟共同设计出的算法[2]该算法被称为LLL算法,可以将一个大的整数向量分解成几个最短的向量之和。该算法在不同的纯数学领域都有应用,已经成为数据加密研究中的重要一环。基于整数向量的密钥被看作是保障未来互联网安全的希望所在,因为和现在常用的密钥不同,基于整数向量的密钥被认为不会被未来的量子计算机破解。

Lovász于2007-2010年任国际数学联合会主席。他还在2014~2020年任匈牙利科学院院长,并在任期内勇于反对匈牙利政府接管科学院下的研究所,但最终未能成功。包括他在内的很多人都认为,政府的接管会影响研究人员的独立性。

从计算到数学

Wigderson于1956年出生于以色列海法。他在以色列和美国完成学业后曾入职多个学术机构,并于1999年加入普林斯顿高等研究院并任职至今。阿贝尔奖在获奖理由中认可了他在几乎所有计算机科学领域的贡献。在这些领域中,他动用了所有能用上的数学工具解决各种各样的问题,甚至是与他研究内容相距甚远的领域。Wigderson对他的领域非常有热情,这种热情具有“传染性”,Sarnak说。“当他和你说话时,你会觉得‘天啊,我最好把手头上的工作放下,改为研究这个’。”

Wigderson最知名的成就之一是阐明了随机性在计算中的作用。在很多情况下,比如寻找迷宫的出口,掷骰子往往能让算法更快地找到解答,但具体原因还不是很清楚。Sarnak说:“如果允许程序进行这种随机选择,那么很多程序都能快很多。”

Wigderson与合作者在90年代证明,如果使用了随机性的算法看起来很高效,那么必定存在另一种同样高效的非随机算法[3]。这从理论上确保了随机算法确实可以找到正确的解答。

Wigderson的另一项重要成果也在信息经济学中发挥着越来越大的影响力。这里要涉及“零知识证明”(zero-knowledge proofs)——这种证明方式可以让一个人在不透露某个论断内容的情况下,证明这条论断的正确性 。

零知识证明对认证比特币一类的数字货币非常重要,还可以帮助验证一个人的身份。也就是说,验证方可以用一系列问题来让对方提供“我知道正确密码”的零知识证明,而不需透露具体密码。1991年,Wigderson与合作者证明[4],本质上所有数学论述都可以改写成支持零知识证明的版本——Wigderson认为,“这可能他最令人惊讶、也最矛盾的结果”。

自从2003年阿贝尔奖创立以来,Lovász是该奖项第三位出生于匈牙利的获奖者,Wigderson是第二位以色列获奖者。除了2019年的Karen Keskulla Uhlenbeck外,阿贝尔奖的获奖者全为男性。

参考文献:

1. Lovász, L. J. Comb. Theory A 25, 319–324 (1978).

2. Lenstra, A. K., Lenstra, H. W. & Lovász, L. Mathematische Ann. 261, 515–534 (1982).

3. Impagliazzo, R. & Wigderson, A. Proceedings of the 29th Symposium on Theory of Computing (STOC) 220–229 (1997).

4. Goldreich, O., Micali, S. & Wigderson, A. J. ACM 38, 691–729 (1991).

原文以Abel Prize celebrates union of mathematics and computer science标题发表在 2021年3月17日的《自然》的新闻版块上

本文来自微信公众号:Nature Portfolio(ID:nature-portfolio),作者:Davide Castelvecchi

Next Post

看了台湾狠人的名字,才知道搞笑是天生的

周五 3月 19 , 2021
系统中可录入名字的地方,最多可容纳50个汉字的长度
登录 注册

热门文章