Lincoln–Vassilevska-Williams–Williams hyperclique conjecture
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.
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
Sign in to submit a solution.
No solutions have been posted yet.