算法与理论计算机2022arxiv.org
FBHHRBNRSSSHK 乘法算法仍未终结
The FBHHRBNRSSSHK-Algorithm for Multiplication is still not the end
专业 · 约 45 分钟读完前置知识：矩阵乘法算法、张量分解、有限域基础
导读
这篇论文回应 DeepMind 在 Nature 上发表的用强化学习搜索矩阵乘法算法的工作（该方法将 5×5 矩阵在 ℤ2 上的乘法从 98 次乘法降到 96 次），作者提出了一种新算法，只需 95 次乘法即可完成同样的任务。作者使用的方法未在本文中详述，将在后续论文《Flip graphs for matrix multiplication》中发表。
HN 关注点：HN 读者刚讨论过 DeepMind 用 AI 发现更快矩阵乘法算法的新闻，而人类数学家随即用传统方法再次刷新纪录，这一'AI 激发人类反超'的进展引发关注。
HN 评论精选
这几条评论里：支持 1 质疑 1 补充 2
补充补充背景：这是对 DeepMind 强化学习成果的回应，改进方法将另文发表
摘要：'针对最近 Nature 文章宣布的 5×5 矩阵在 ℤ2 上仅需 96 次乘法的算法（比此前纪录少 2 次），我们提出一个只需 95 次乘法的算法。'那篇 Nature 文章正是 DeepMind 用强化学习引导搜索更优矩阵乘法算法的工作。他们是在 DeepMind 算法基础上，用自己的一套方法（本文未详述，将发表于后续论文《Flip graphs for matrix multiplication》）做出改进的。
telotortium查看英文原文
Abstract: "In response to a recent Nature article which announced an algorithm for multiplying 5×5-matrices over ℤ2 with only 96 multiplications, two fewer than the previous record, we present an algorithm that does the job with only 95 multiplications." The "recent Nature article" is, of course, Deepmind's reinforcement learning-guided search for better matrix multiplication algorithms: https://news.ycombinator.com/item?id=33096580. They improved upon Deepmind's algorithms by applying a method of their own, which is not described in this paper, but which they will publish in an upcoming paper: "Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. in preparation."
支持深度学习的进展激励了经典方法的突破，类似现象在物理学中也出现过
我很喜欢这一点：现代方法（深度学习）的进步反过来推动了经典方法的进步。类似的事情在物理学中也发生过——量子算法的进展促使研究者找到了更好的经典算法。科学不是竞赛！
alexmolas查看英文原文
I love how advances in modern approaches (deep learning) push for advances in classical approaches. Something similar happened in physics, where advances in quantum algorithms made researchers to find better classical algorithms. Science is not a competition!
质疑提问：矩阵乘法算法的理论下界是否可知、是否可判定
我很好奇我们什么时候能证明某个矩阵乘法问题已经找到了最快的算法。存在理论下界吗？（就 5×5 这种有限情形而言，确实存在实际下界，但渐近情形呢？）确定理论下界会不会是某种不可判定或 NP 难的问题？我们对此了解多少？
ajkjk查看英文原文
I'm really interested to know when we will be able to prove that we have the fastest algorithm for some matrix multiplication problem. Is there a theoretical lower bound? (well in this case, for 5x5, there's gonna be an actual lower bound. but for asymptotic cases..?) Is figuring out the theoretical lower bound some kind of undecidable/NP problem? what do we know about it?
补充类比：纪录一旦被打破，很快就会被再次刷新
这有点像 Bannister 打破尘封十年的 4 分钟一英里跑纪录后，仅 6 周就有人再次刷新他的纪录。
jeffbee查看英文原文
This is a bit like the way that Bannister broke a decade-old record with his 4-minute mile, then someone beat his record 6 weeks later.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2022Hacker News 讨论帖168 分 · 87 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选