Hypergraphic planted-clique conjecture
For every fixed integer and every constant , let be a random -uniform hypergraph on vertices in which each -element hyperedge is present independently with probability , and let be obtained by first choosing a uniformly random set of vertices and then ensuring that every -element subset of this set is a hyperedge. The hypergraphic planted-clique conjecture asserts that no randomized polynomial-time algorithm distinguishes from with non-negligible advantage as ; equivalently, for every randomized polynomial-time algorithm , .
References
- Tracking a Small Set of Experts in Online Convex Optimization — arXiv — Angelos Assos, Anand Brahmbhatt, Elad Hazan
Source: arXiv
Progress summary
The conjecture remains unproved; a recent paper only uses it as a hardness assumption to obtain a conditional learning lower bound.
For fixed , the conjecture says that detecting a planted clique in a random -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 is the ordinary planted-clique conjecture.
Known results
- Exhaustive search succeeds near the statistical threshold, of order .
- SVD-based methods detect planted cliques for but fail at .
- Luo and Zhang (2020) established barriers for Metropolis and low-degree-polynomial algorithms when , 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.
Solutions 0
No solutions have been posted yet.