The k-planted clique detection conjecture
Statement
Fix a constant . Let be a fixed known partition of into equally sized subsets, and under the alternative choose exactly one planted clique vertex uniformly from each part. Let denote the resulting detection problem, with hypotheses and . For randomized polynomial-time algorithms and positive-integer sequences satisfying
the -planted clique conjecture. If is an instance of , then
This is a planted-clique hardness assumption with secret leakage: the algorithm knows the partition, while the planted set contains one uniformly selected vertex from each part. The supplied text gives no evidence that the conjecture has been resolved.
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.