2021年阿贝尔奖公布！理论计算机科学和离散数学领域学者获奖

3月17日，2021年阿贝尔奖揭晓。挪威科学和文学院决定将2021年阿贝尔奖授予来自匈牙利，布达佩斯罗兰大学的László Lovász 和来自美国，普林斯顿高等研究院的 Avi Wigderson，以表彰两位科学家在理论计算机科学和离散数学方面做出的杰出贡献，以及在将之塑造为现代数学中心领域中发挥的主导作用。获奖者将分享750万挪威克朗的奖金（约合575万人民币）。

理论计算机科学 (TCS) 是研究计算的能力和局限性的科学。其根源可追溯至 Kurt Gödel、AlonzoChurch、Alan Turing 和 John von Neumann 所做的基础性研究，这些研究推动了真正的物理计算机的发展。TCS 包含两个互补的分支学科，即算法设计（为大量计算问题开发有效方法）和计算复杂性（证明算法效率的固有限制）。

自然离散数学和 TCS 一直是紧密联系的两个领域。虽然这两个领域都从更传统的数学领域中获益匪浅，但其对传统数学领域的反向影响也越来越大。 TCS 的应用、概念和技术带来了新的挑战，开辟了新的研究方向，解决了纯数学和应用数学中的重要开放性问题。

László Lovász（左）和Avi Wigderson

在过去几十年中，Lászlé Lovász 和 Avi Wigderson一直是推动实现相关发展的主导力量。Lászlé Lovász 与 Arjen Lenstra 和 Hendrik Lenstra一起开发出了 LLL 格基约减算法。给定一个高维整数格（网格），此算法可以为之找到一个不错的近乎正交基。除了因式分解有理多项式的算法等一些应用之外，LLL 算法也是一个受密码专家欢迎的工具，并成功破解了所提出的几个加密系统。令人惊讶的是，LLL 算法的分析还用于设计和保证较新的格基加密系统的安全性，这些系统甚至能够抵御量子计算机的攻击。

Avi Wigderson 对计算复杂性的各个方面，特别是随机性在计算中的作用，做出了广泛而深刻的贡献。随机算法是指通过抛硬币的方法，以高概率计算正确解的算法。Wigderson雨合作者证明了P=BPP这一猜想，这意味着每一种随机算法都可以去随机化。Wigderson与Impagliazzo 和 Valentine Kabanets 的后续研究进一步证明了即使是对于有已知的随机算法的具体问题，有效的确定性算法也意味着必须存在这样一个难解的问题。

阿贝尔委员会主席 Hans Munthe-Kaas 表示，“在过去几十年中，Lovász 和 Wigderson 一直是推动实现相关发展的主导力量。他们的研究在很多方面是相互交错的，并都对理解计算中的随机性和探索高效计算的边界做出了巨大贡献。”

他说：“正是由于这两位所做出的突破性贡献，离散数学和相对“年轻”的理论计算机科学领域现已牢固确立为现代数学的中心领域。

关于阿贝尔奖 Abel prize

阿贝尔奖设立于2002年1月1日，于2003年6月3日首次颁发。阿贝尔奖与菲尔兹奖、沃尔夫奖并称为国际最高数学“三大奖”。