← All problems

Hypergraphic planted-clique conjecture

For every fixed integer d≥2d\ge 2 and every constant τ>0\tau>0, let H0H_0 be a random dd-uniform hypergraph on NN vertices in which each dd-element hyperedge is present independently with probability 1/21/2, and let H1H_1 be obtained by first choosing a uniformly random set of κ=⌊N1/2−τ⌋\kappa=\lfloor N^{1/2-\tau}\rfloor vertices and then ensuring that every dd-element subset of this set is a hyperedge. The hypergraphic planted-clique conjecture asserts that no randomized polynomial-time algorithm distinguishes H0H_0 from H1H_1 with non-negligible advantage as N→∞N\to\infty; equivalently, for every randomized polynomial-time algorithm AA, ∣Pr⁡[A(H1)=1]−Pr⁡[A(H0)=1]∣=o(1)\left|\Pr[A(H_1)=1]-\Pr[A(H_0)=1]\right|=o(1).

References

Source: arXiv

Progress summary

Refreshed
Open

The conjecture remains unproved; a recent paper only uses it as a hardness assumption to obtain a conditional learning lower bound.

For fixed d≥2d \ge 2, the conjecture says that detecting a planted clique in a random dd-uniform hypergraph is computationally hard when the clique is below the conjectured polynomial-time threshold. Luo and Zhang formulated this hypergraphic version in 2020; the case d=2d=2 is the ordinary planted-clique conjecture.

Known results

  • Exhaustive search succeeds near the statistical threshold, of order ((d!+ϵ)log⁡2N)1/(d−1)\left((d!+\epsilon)\log_2 N\right)^{1/(d-1)}.
  • SVD-based methods detect planted cliques for κ=Ω(N)\kappa=\Omega(\sqrt{N}) but fail at κ=N1/2−ϵ\kappa=N^{1/2-\epsilon}.
  • Luo and Zhang (2020) established barriers for Metropolis and low-degree-polynomial algorithms when κ=O(N1/2−τ)\kappa=O(N^{1/2-\tau}), evidence rather than a proof against all polynomial-time algorithms.
  • The reverse reduction from ordinary to hypergraphic planted clique remains open.

October 2026 conditional lower bound

Assos, Brahmbhatt, and Hazan derive a conditional computational lower bound for tracking a small set of experts in online convex optimization, assuming the hypergraphic planted-clique conjecture. This is an application of the conjecture, not evidence that the conjecture itself has been proved or refuted.

Current status (as of October 2026): The hypergraphic planted-clique conjecture remains open; known algorithmic barriers and conditional applications do not establish its computational-hardness claim.

Sources

Solutions 0

No solutions have been posted yet.