Planted Clique Conjectures are Equivalent

Planted Clique Conjecture states that no polynomial-time algorithm can find a k-clique in an n-vertex Erdos-Renyi random graph with a k-clique planted for k << n^{1/2}. We present the equivalence among many variants of planted clique conjectures, including search versions of a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), and decision versions with small and large probabilities. In particular, this equivalence identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability k^2/n for any k <= n^{1/2}. We show that for *any* k, no polynomial-time algorithm can distinguish these two random graphs with probability significantly larger than k^2/n *if and only if* the planted clique conjecture holds.

Joint work with Nobutaka Shimizu.