阿贝尔奖庆祝数学和计算机科学的结合

计算理论的两位先驱获得了2021年的阿贝尔奖，这是数学界最负盛名的荣誉之一。

匈牙利数学家LászlóLovász和以色列计算机科学家Avi Wigderson将分享这一价值750万挪威克朗（88.6万美元）的奖项，挪威科学与文学学院于3月17日宣布：“感谢他们对理论计算机科学和离散数学的基础性贡献，以及他们在将其塑造成现代数学的中心领域方面发挥的主导作用。”。新泽西州普林斯顿高等研究所（IAS）的维格德森告诉《自然》杂志说，这个奖验证了计算理论，而不仅仅是他自己的工作。“我认为这对这一领域意义重大，”他说，“如今，区分纯数学和应用数学越来越困难，我认为这是一个很好的发展，”洛瓦兹说，谁是布达佩斯的E?tv?s Loránd大学的教授。

算法——包括孩子们在学校学习的简单程序，比如长除法——至少从古希腊时代起就一直是数学的核心。但是自从二十世纪计算机出现以来，研究的重点已经从“一个算法能解决这个问题吗？”？一个算法，至少在原则上，能在实际的计算机上，在合理的时间内解决这个问题吗？“

Lovász和Wigderson在这些发展中发挥了核心作用，IAS的数字理论家peter Sarnak说。“算法复杂性理论和解决问题速度的研究是在60年代和70年代发展起来的，这两位研究员都被证明是绝对的领导者。”

Lovász 1948年出生于布达佩斯，成长在一个鼓励天才儿童竞争解决难题的环境中。他的早期灵感大多来自现代最多产的数学家保罗·埃尔德斯。Erd?的工作重点是离散对象及其关系的数学，例如网络中的节点，而不是几何等领域典型的连续变量，布达佩斯阿尔弗雷尼数学研究所的数学家帕尔菲（péter pál pálfy）说，

Lovász开始他的职业生涯之时，离散数学的主题，如网络理论——曾经被“纯粹”数学家所轻视——对数学的其他领域和应用都变得至关重要比如“大数据”的分析。他对基础研究及其应用很感兴趣，并在微软担任了7年的全职研究员。他解决了网络数学理论中的主要问题，例如，计算为节点着色的可能方法的数量，同时确保任何两个相邻节点总是不同的颜色1他与两位荷兰数论家Arjen和Hendrik Lenstra兄弟共同设计的算法。该算法被称为LLL，它将一个由整数组成的大向量分解为这种类型的最短向量之和。它在纯数学的各个领域都有应用，已经成为研究数据加密的关键。基于整数向量的加密密钥被认为是未来互联网安全的一个前景，因为与当今通信中常用的密钥不同，人们认为它们不会受到被未来的量子计算机破解。2007年至2010年，洛瓦兹担任国际数学联合会主席。2014年至2020年，他还领导了匈牙利科学院，在这几年中，他领导了一个大胆但最终失败的努力阻止匈牙利政府接管学院的研究机构。他和其他许多人认为，此举将降低研究人员的独立性

威格森1956年出生于以色列海法。他曾在以色列和美国学习，并在1999年进入国际会计学院之前担任过各种学术职务。他在《阿贝尔奖》中的获奖表彰了他在计算机科学几乎所有领域的贡献，在这些领域里，他用他所能找到的任何数学工具来解决任何问题，甚至是从遥远的研究领域。萨纳克说，维格德森对其研究领域的热情是“有感染力的”。“当他和你说话的时候，你几乎会觉得‘天哪，我最好放下我正在做的事情，开始研究这个问题’”

维格森最著名的成就之一就是阐明了随机性在计算中的作用。在许多情况下，例如寻找走出迷宫的方法，比喻硬币翻转允许算法快速找到解决方案，但原因不是很明显。萨纳克说：“如果你允许许多程序做这种随机选择，那么它们实际上运行得更快。上世纪90年代，Wigderson在与合作者合作时指出，如果一种使用随机性的算法似乎能有效运行，那么另一种算法，必须存在几乎同样有效的非随机算法3。这从理论上保证了随机算法确实能找到正确的解决方案。

维格森的另一项主要工作与信息经济越来越相关。它涉及“零知识证明”，一种允许某人验证语句正确性的方法，而不必透露有关语句所说内容的任何信息。

零知识证明对认证数字货币，如比特币，也可以帮助验证一个人的身份。通过回答验证者的问题，有人可以给出一个零知识证明有一个正确的密码，例如，没有透露密码本身。Wigderson和他的合作者在1991年表明，基本上所有的数学陈述都可以以一种零知识证明的方式翻译——“可能是最令人惊讶的，威格森说，他的研究结果中最“矛盾”的是。

自2003年阿贝尔奖揭晓以来，洛瓦兹是第三位匈牙利裔获奖者，维格德森是第二位以色列人。除了Karen Keskulla Uhlenbeck在2019年，到目前为止所有获奖者都是男性

备注：

零知识证明(Zero—Knowledge proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用。如果能够将零知识证明用于验证，将可以有效解决许多问题。

doi: https://doi.org/10.1038/d41586-021-00694-9