← 研踪 PaperTrailarXiv:2611.03880 · v1
The Hyperclique Hypothesis is False
首次提交 2026-11-03 03:51
版本更新 2026-11-03 03:51
雷达观测 2026-11-04 23:40
摘要
The Hyperclique Hypothesis postulates that, for all constants $k > h \geq 3$, detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices requires time $n^{k-o(1)}$. This hypothesis is false: there is an algebraic algorithm that detects (and even counts) $k$-cliques in $h$-uniform hypergraphs in time $O(n^{(1-ε_h)k})$. Via known reductions, this also refutes the recently proposed $k$-AP Hypothesis. As a consequence, many problems with conditional lower bounds based on these two hypotheses may admit faster algorithms after all. This result is almost entirely due to AI.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-03 03:51 · 最新观测版本
The Hyperclique Hypothesis is False
The Hyperclique Hypothesis postulates that, for all constants $k > h \geq 3$, detecting a $k$-clique in an $h$-uniform hypergraph with $n$ vertices requires time $n^{k-o(1)}$. This hypothesis is false: there is an algebraic algorithm that detects (and even counts) $k$-cliques in $h$-uniform hypergraphs in time $O(n^{(1-ε_h)k})$. Via known reductions, this also refutes the recently proposed $k$-AP Hypothesis. As a consequence, many problems with conditional lower bounds based on these two hypotheses may admit faster algorithms after all. This result is almost entirely due to AI.
查看此版本解读 →查看此版本原文 ↗