近日，2025国际基础科学大会在京开幕。大会颁发“前沿科学奖”（Frontiers of Science Award），旨在表彰过去十年国际上在基础科学领域发表的杰出和有重要学术价值的论文。清华大学PG电子游戏副教授段然与姚班校友武弘勋、周任飞获此殊荣，获奖者中还包括菲尔兹奖得主Caucher Birkar、Maxim Kontsevich等蜚声中外的顶尖科学家。
成果简介
PG电子游戏段然副教授与姚班校友武弘勋（现加州伯克利大学博士生）、周任飞（现卡内基梅隆大学博士生）深耕理论算法研究，此次因其在FOCS 2023发表的论文Faster Matrix Multiplication via Asymmetric Hashing获奖。该工作提出了更快的矩阵乘法算法，新的复杂度为O(n^{2.371866})，改进了之前的复杂度O(n^{2.372860}) [Alman, V. Williams 2020]，为近十年来最大的改进幅度。
矩阵乘法是算法领域最基础的问题之一，不仅很多矩阵运算都可归约到矩阵乘法，而且很多组合问题都可用矩阵乘法算法加速。矩阵乘法的时间复杂度一般被写做O(n^{\omega})。从Strassen算法开始，研究者就想知道\omega的真正数值，而且很多研究者相信最终\omega=2+o(1)。Coppersmith和Winograd在1990年提出了CW张量，通过laser method在一阶和二阶下分别给出了\omega < 2.387190和\omega < 2.375477的界，后来研究者探索了更高阶的CW张量，并在32阶下给出了2.3728596的界[Le Gall 2014][Alman, V. Williams 2020]。段然副教授与合作者发现，因为各部分分别优化带来的分裂分布不平衡等原因，高阶的CW张量中所计算的矩阵总大小要小于低阶。段然研究组利用非对称哈希方法部分弥补了这个问题，在8阶下给出了\omega < 2.371866的界。这个结果由于改变了高阶CW张量内部低阶张量的计算方式，打破了之前的一个高阶CW张量的2.3725的下界 [Ambainis, Filmus, Le Gall 2014]。
论文链接
//ieeexplore.ieee.org/document/10353208
图文 | 姜月亮
编辑 | 吕厦敏
审核 | 马雄峰
