3SUM 问题最快确定性算法刷新:n^1.9961 突破 n²
basedjensen · x · 2026-10-10
研究者宣布 3SUM 问题确定性算法新纪录:运行时间降至 n^1.9961,这是首个有零随机性、且追平最优随机算法界的结果,比 n² 节省 4.5 倍。核心进展基于 Josh Alman 与 Virginia Vassilevska Williams 的论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》,利用稀疏偏侧图中的三角形结构,同时给出 3SUM 与 APSP 的亚三次方结果,被认为是细粒度复杂度领域的重大突破。
「研究」频道最新
- 用向量数据库替换权重矩阵,提出检索中心深度学习 — RobertTLange · 2026-10-10
- 上交大 UVTA 用 1000 条人类触觉示范教会机器人灵巧操作 — siyuanhuang95 · 2026-10-10
- 20 分钟讲透特斯拉 FSD:8 摄像头 36 帧,20 亿信息炼成两个输出 — PTrubey · 2026-10-10
- 21位学者联署白皮书：视觉通用智能能否通向AGI — HirokatuKataoka · 2026-10-10
- Epoch AI:三个数学子领域超半数 arXiv 论文已承认使用 AI — burny_tech · 2026-10-10
- 学者批评 Transformer 教学图示:自注意力总被画成黑盒方块 — PlisSergey · 2026-10-10