曾被“纯”数学家看不起的研究，摘得数学界“诺贝尔奖”
本文来自微信公众号：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日的《自然》的新闻版块上