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

2

3月17日,2021年阿贝尔奖揭晓。挪威科学和文学院决定将2021年阿贝尔奖颁布来自匈牙利,布达佩斯罗兰大学的László Lovász 和来自美国,普林斯顿高级研讨院的 Avi Wigderson,以赞誉两位科学家在理论核算机科学和离散数学方面做出的杰出奉献,以及在将之刻画为现代数学中心范畴中发挥的主导效果。获奖者将共享750万挪威克朗的奖金(约合580万人民币)。

理论核算机科学 (TCS) 是研讨核算的才能和局限性的科学。其本源可追溯至 Kurt Gödel、AlonzoChurch、Alan Turing 和 John von Neumann 所做的基础性研讨,这些研讨推进了真实的物理核算机的开展。TCS 包括两个互补的分支学科,即算法规划(为许多核算问题开发有用办法)和核算复杂性(证明算法功率的固有约束)。

天然离散数学和 TCS 一直是紧密联系的两个范畴。尽管这两个范畴都从更传统的数学范畴中获益匪浅,但其对传统数学范畴的反向影响也越来越大。 TCS 的使用、概念和技能带来了新的应战,拓荒了新的研讨方向,处理了纯数学和使用数学中的重要敞开性问题。

1

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日初次颁布。阿贝尔奖与菲尔兹奖、沃尔夫奖并称为世界最高数学“三大奖”。