跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1084新增论文
+883其中 AI 相关
+130已有论文修订
+94新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-18 19:45各信源进度 →

统计口径与数据新鲜度

统计 2026-11-18 06:25 — 2026-11-19 06:25(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-18 19:45库内论文最新更新时间:2026-11-18 08:00

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

26,870 已收录论文22,374 AI 相关8,156 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 2 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
版本更新 · v2arXiv:2610.42012

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized

Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu

原文摘要

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for $k$-SUM for integer inputs for odd constant $k$ in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant $\varepsilon_k>0$, disproving the $k$-SUM Hypothesis for all odd $k$. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

cs.DS

新论文 · v1arXiv:2611.06813

3-一致超团假设为假

The 3-Uniform Hyperclique Hypothesis is False

Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu

AI 速读 基于摘要

作者给出检测或计数3-一致超图中4-超团的真正次四次算法,从而否证细粒度复杂性中一个流行假设。

cs.DS

查看原文摘要

We present truly subquartic algorithms for detecting or counting 4-hypercliques in a 3-uniform hypergraph with $n$ vertices, disproving a popular hypothesis in fine-grained complexity. The result immediately implies a faster algorithm for finding a $k$-hyperclique in a 3-uniform hypergraph for all constant $k\ge 4$, and a faster exponential-time algorithm for Max-3-SAT.