The k-partite planted clique conjecture
Statement
Fix a constant . Let and be increasing sequences of positive integers such that and divides , and let
be a sequence of randomized polynomial-time algorithms. Under , is sampled from the null distribution, while under it is sampled from the -partite planted-clique distribution . -partite planted clique conjecture. If is an instance of , then
Thus no such sequence of algorithms distinguishes the planted and null distributions with asymptotic error sum below ; this is the formal hardness assumption used by the paper's reductions, and the source gives no resolution.
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.