2021年阿贝尔奖获得者László Lovász。图片来源：Hungarian Academy of Sciences/Laszlo Mudra
上个世纪70年代，当 Avi Wigderson 和 László Lovász 开始他们的职业生涯时，理论计算机科学和纯数学几乎是完全分开的学科领域。经过几十年的发展，这两个学科之间早已变得极为密切，我们甚至很难分清它们之间的界限。今天，Wigderson和Lovász二人因其在理论计算机科学和离散数学所作出的基础性贡献，获得了数学领域的最高奖之一——阿贝尔奖。
编译 | 佐 佑
理论计算机科学研究的是计算的能力和局限，其根源可追溯到库尔特·哥德尔、阿隆佐·丘奇、阿兰·图灵，以及约翰·冯·诺伊曼的基础工作，这些工作为真正的物理计算机研究的发展奠定了坚实的基础。理论计算机科学包含了两个互补的子学科，一个是算法设计，另一个是计算复杂性。前者涉及到为大量的计算问题开发有效的方法，后者展示了算法效率存在固有的局限性。20世纪60年代，Alan Cobham 等人提出了多项式时间算法的概念，Stephen Cook 等人提出了著名的P≠NP猜想。这些工作对整个领域以及Lovász和Wigderson的工作，都产生了重大影响。理论计算机科学是密码学的基础，且它对其他一些科学领域的影响正日渐明显。图形、字符串、排列等离散结构都是理论计算机科学的核心，离散数学和理论计算机科学也自然成了紧密相关的领域。虽然这两个领域都从传统的数学领域中获益良多，但现在反向的影响也越来越大。理论计算机科学所带来的应用、概念和技术，激发了更多新的挑战，开辟了新的研究方向，并解决了纯数学和应用数学中的一些重要的未解难题。在过去的几十年里，Lovász和Wigderson一直是这一领域中的领军人物。他们的工作在许多方面都有交叉，尤其是他们都为理解计算中的随机性，以及探索高效计算的边界，做出了杰出贡献。
1948年，Lovász出生于匈牙利布达佩斯。年轻时的Lovász就已是数学界的一颗闪耀新星，他在十几岁时就在国际数学奥林匹克竞赛上获得了三枚金牌。Lovász最具影响力的成果之一，就是与Arjen Lenstra和Hendrik Lenstra 一起创立了以他们三人名字命名的LLL算法。这是最基本的算法之一，它不仅在理论上很重要，在很多实际用途上也很重要。LLL算法适用于被称为格的几何对象，格指的是在空间中其坐标值通常为整数值的点集。LLL算法解决了关于格的属性的一个基本问题：格中的哪个点离原点最近？这是一个难以解决的问题，尤其是在高维空间中，以及格中的点会形成失真的形状时。LLL算法不能精确地解答这个问题，但却能找到一个很好的近似。它能确定一个点，并保证没有其他任何点比这个点更接近原点。这一几何模型有着广泛的适用性，找到这个点在许多应用场景中都有重要意义。LLL算法除了能分解有理多项式等应用之外，它还是密码专家最喜欢的工具，它已成功地破解了几个密码系统。而令人称奇的是，对LLL算法的分析也能被用于设计和保证更新的基于格的密码系统（甚至可抵挡量子计算机的攻击）的安全性。LLL算法只是Lovász众多有远见的贡献之一。除了LLL算法，这位高产的数学家还证明了局部引理；展示了如何有效地解决半定规划，由此引领了一场算法设计的革命；他为随机漫步理论及其在欧几里得等周问题和高维物体近似体积计算中的应用做出了贡献；他与 Uriel Feige 等人发表的论文证明了一个早期版本的概率可检测证明定理（PCP定理）；他还解决了长期存在的完美图猜想、Kneser猜想等问题，并在近年来发展了图极限理论。
2021年阿贝尔奖获得者 Avi Wigderson。图片来源：Dan Komoda/Institute for Advanced Study, Princeton, NJ USA
Wigderson于1956年出生在以色列海法。在他十几岁时，计算机科学家们才刚刚开始勾画复杂性理论的基本框架。复杂性理论关注的是算法的速度和效率，它涉及到根据算法解决计算问题时的难度对问题进行分类。Wigderson对计算复杂性的各个方面都做出了广泛而深刻的贡献，尤其是随机性在计算中的作用。在过去的几十年里，一些研究人员为许多问题发展了确定性算法，而此前只有随机算法是已知的。由Agrawal等人提出的确定性算法的素数检测就是去随机化算法的一个显著例子。这样的去随机化的成果，让数学家们开始思考随机性是否真的重要的问题。在20世纪90年代发表的两篇论文中，Wigderson和他的合作者证明了在特定的假设下，答案很可能是否定的。他们提出了一个有点类似于P≠NP的猜想，P=BPP，这个等式意味着每个随机算法都可以被去随机化，并转化为具有可观效率的确定性算法；此外，去随机化是通有且普遍的，它不依赖于随机化算法的内部细节。
另一种看待这项工作的方式是将其视为难度和随机性之间的权衡：如果存在一个足够困难的问题，那么随机性就可以通过高效的确定性算法进行模拟。Wigderson随后证明了与之相反的观点，他得出的结论认为：即使是针对具有已知随机算法的特定问题的有效确定性算法，也意味着一定存在这样一个困难问题。这一工作与伪随机（看起来随机）的对象紧密相关。Wigderson的工作构建了伪随机生成器，它将几个真正随机的比特变成许多伪随机比特，从一个不完美的随机源中提取出近乎完美的随机比特。他与 Omer Reingold 以及 Salil Vadhan 一起发展出的锯齿形图积，启发了 Irit Dinur 对PCP定理的组合证明，以及Reingold对图连通性问题的高效存储算法。Wigderson的贡献还不止于此，他对密码学基础的贡献，为无需通过任何物理手段发展出像在线扑克游戏一样复杂的协议奠定了基础。他在交互式证明系统方面的研究，尤其是在 “零知识证明” 这一悖论式的概念上的研究，最近已经被用于区块链技术和数字货币上。工业、医药、在线通信、电子商务和经济中的数字创新，全部都依赖于算法和复杂性理论的研究。这些想法彻底改变了科学领域，而这仅仅是个开始。像Wigderson和Lovász这样的学者将继续对这些基础性问题及其潜在影响进行研究。在Lovász和Wigderson的领导下，离散数学和相对年轻的理论计算机科学领域现正在逐渐成为现代数学的中心。
参考资料：
https://www.abelprize.no
京公网安备 11010502034662号 