拉兹洛·洛瓦兹
在图论、组合优化与理论计算机科学的奠基性贡献,提出 LLL 格规约算法与图极限(graphon)理论
获奖原因
拉兹洛·洛瓦兹是组合数学与理论计算机科学的桥梁人物。他与 Lenstra、Lenstra 共同提出 LLL 算法(格基规约),成为密码学与分析数论的基本工具;他证明了”洛瓦兹局部引理”、Erdős–Ko–Rado 型极值定理,并开创了”图极限”理论(以 graphon 描述稠密图序列的极限)。2021 年他与阿维·维格森共享阿贝尔奖。
洛瓦兹的工作把组合结构变成可计算、可分析的对象。LLL 算法能在多项式时间内找到格中”足够短”的向量,直接用于整数规划、密码攻击与最近点问题;图极限理论则用对称可测函数 (graphon)刻画大图序列的渐近结构,使极值图论与统计网络分析统一起来。他还与埃尔德什、以及后来的塞迈雷迪在匹配理论、完美图、随机图方法上贡献卓著,是现代离散数学当之无愧的旗手。