新论文 · v1arXiv:2611.06813
3-一致超团假设为假
The 3-Uniform Hyperclique Hypothesis is False
Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
AI 速览：作者给出检测或计数3-一致超图中4-超团的真正次四次算法，从而否证细粒度复杂性中一个流行假设。
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.
cs.DS