Lincoln–Vassilevska-Williams–Williams hyperclique conjecture

From papers

Let k>r3k>r\geq 3 and let an rr-uniform hypergraph be a hypergraph whose edges have size rr. A kk-hyperclique is a set of kk vertices such that every rr-subset is an edge. The Lincoln–Vassilevska-Williams–Williams hyperclique conjecture states that, for every k>r3k>r\geq 3 and every ε>0\varepsilon>0, kk-hyperclique detection in rr-uniform hypergraphs cannot be solved in

O(nkε)O(n^{k-\varepsilon})

time. This conjecture underlies conditional lower bounds in fine-grained complexity, and the source notes that several breakthroughs would follow if it were false.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Or Zamir, “Algorithmic Applications of Hypergraph and Partition Containers”, arXiv:2211.11737 (2022).

Solutions 0

No solutions have been posted yet.