拉兹洛·洛瓦兹

在图论、组合优化与理论计算机科学的奠基性贡献,提出 LLL 格规约算法与图极限(graphon)理论

奖项
阿贝尔奖
年份
2021
国籍 / 出生
匈牙利
出生
1948

获奖原因

拉兹洛·洛瓦兹是组合数学与理论计算机科学的桥梁人物。他与 Lenstra、Lenstra 共同提出 LLL 算法(格基规约),成为密码学与分析数论的基本工具;他证明了”洛瓦兹局部引理”、Erdős–Ko–Rado 型极值定理,并开创了”图极限”理论(以 graphon 描述稠密图序列的极限)。2021 年他与阿维·维格森共享阿贝尔奖。

洛瓦兹的工作把组合结构变成可计算、可分析的对象。LLL 算法能在多项式时间内找到格中”足够短”的向量,直接用于整数规划、密码攻击与最近点问题;图极限理论则用对称可测函数 W:[0,1]2[0,1]W:[0,1]^2\to[0,1](graphon)刻画大图序列的渐近结构,使极值图论与统计网络分析统一起来。他还与埃尔德什、以及后来的塞迈雷迪在匹配理论、完美图、随机图方法上贡献卓著,是现代离散数学当之无愧的旗手。