Lincoln–Vassilevska-Williams–Williams hyperclique conjecture
Let and let an -uniform hypergraph be a hypergraph whose edges have size . A -hyperclique is a set of vertices such that every -subset is an edge. The Lincoln–Vassilevska-Williams–Williams hyperclique conjecture states that, for every and every , -hyperclique detection in -uniform hypergraphs cannot be solved in
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
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.