aifollow.news
Back Rohan Paul
Rohan Paul· @rohanpaul_ai · X· · Original publication time AI score68

Post says Claude found faster methods for 3SUM and all-pairs shortest pathsMachine translation

AI introduction

A post describing a Columbia and MIT paper says Claude found a way to compute selected entries in the product of two long, thin matrices while skipping some work done by a classic method. It reports running times of O(n^1.9992) for 3SUM and O(n^2.9995) for all-pairs shortest paths, describing the gains as tiny.

Original post · AI translation

@rohanpaul_ai
Translation · refer to the original

– https://arxiv.org/abs/2610.06783

标题:“通过稀疏非对称图中的三角形实现真正次二次时间的 3SUM 和真正次三次时间的 APSP”

ReplyRohan Paul@rohanpaul_ai
Translation
哥伦比亚大学和麻省理工学院的一篇新论文表明,Claude 发现的一种算法突破了 3SUM 和所有点对最短路径问题长期以来的运行时间界限。 3SUM 问的是,一个列表中是否有 3 个数相加等于 0;所有点对最短路径问题要求求出图中每对顶点之间的距离。几十年来,没有人能将教科书中的二次时间和三次时间算法改进到超出微小幅度,许多人认为这根本不可能。 Claude 找到了一种更快的方法,计算 2 个细长矩阵乘积中选定的元素,省去了经典方法会做的部分计算。随后,利用已知的归约方法,可以将其转化为 3SUM、最短路径及许多相关问题的加速算法。 3SUM 现在可以在 O(n^1.9992) 时间内求解,最短路径问题可以在 O(n^2.9995) 时间内求解。这些提升虽然很小,但仍推翻了 3SUM 和 APSP 猜想。Claude 在 1 次会话中使用 16M 个输出 token,在无人类输入的情况下找到了这一方法。 将算法中“已知很难突破”的界限视为 AI 搜索的开放目标,并像这篇论文使用 Lean 4 所做的那样,对 AI 发现的证明进行形式化检验。
Original

New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits for 3SUM and all-pairs shortest paths. 3SUM asks whether 3 numbers in a list sum to 0, and all-pairs shortest paths asks for every distance in a graph. For decades, nobody beat textbook quadratic and cubic time by more than tiny factors, and many assumed nobody could. Claude found a faster way to compute selected entries of a product of 2 long, thin matrices, skipping work a classic method does. Known reductions then turn this into speedups for 3SUM, shortest paths, and many related problems. 3SUM now runs in O(n^1.9992) time and shortest paths in O(n^2.9995), tiny gains that still refute the 3SUM and APSP hypotheses. Claude found the method in 1 session using 16M output tokens with no human input. Treat "known hard" algorithm limits as open targets for AI search, and check AI-found proofs formally, as this paper did with Lean 4.

View this post on X ↗

Source: Rohan Paul · x.com

Research
Found an error? Send a correction