← 研踪 PaperTrailarXiv:2611.06813 · v1
The 3-Uniform Hyperclique Hypothesis is False
首次提交 2026-11-05 01:25
版本更新 2026-11-05 01:25
雷达观测 2026-11-05 12:12
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 01:25 · 最新观测版本
The 3-Uniform Hyperclique Hypothesis is False
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.
查看此版本解读 →查看此版本原文 ↗