The planted clique detection conjecture
Statement
Let be constant. For each , let be a randomized polynomial-time algorithm, and let be a sequence of positive integers satisfying
For the planted clique detection problem, with null hypothesis and alternative hypothesis , the planted clique detection conjecture. Every such sequence of algorithms satisfies
This is the standard planted-clique hardness assumption underlying reductions for statistical-computational gaps; it asserts that polynomial-time algorithms cannot achieve nontrivial detection when the planted clique has size with .
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.