Lincoln–Vassilevska-Williams–Williams hyperclique conjecture

About 4 years old · traced to

Let k>r≥3k>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>r≥3k>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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.