Hypergraph planted clique conjecture
Statement
Let -uniform hypergraphs on the vertex set be hypergraphs whose hyperedges are incident on vertices. Under the null model, let , where each hyperedge is included independently with probability . Under the planted model, let , where vertices are chosen uniformly at random, all hyperedges among them are included, and every remaining hyperedge is included independently with probability . For a test , define
Hypergraph planted clique conjecture. Suppose that and that is a fixed integer. If
then for every sequence of tests computable in time polynomial in ,
This is the assumed computational hardness of detecting a planted clique in a random -uniform hypergraph below the scale, and it serves as the primitive for the paper's lower bounds on polynomial-time adaptation. No resolution status is supplied in the source.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.