Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-058 | 29th March 2024 15:28

Planted Clique Conjectures Are Equivalent


Authors: Shuichi Hirahara, Nobutaka Shimizu
Publication: 31st March 2024 17:01
Downloads: 520


The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size $k \ll \sqrt{n}$ in an $n$-vertex Erd\H{o}s--R\'enyi random graph with a $k$-clique planted. In this paper, we prove the equivalence among many (in fact, \emph{most}) variants of planted clique conjectures, such as search versions with 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), decision versions with small and large success probabilities, and decision versions with adversarially chosen $k$ and binomially distributed $k$. In particular, we establish the equivalence between the planted clique problem introduced by Jerrum and Ku\v{c}era and its decision version suggested by Saks in the 1990s. Moreover, the equivalence among decision versions 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 $\Theta(k^2/n)$ for any $k \le \sqrt{n}$. We show that for \emph{any} $k$, no polynomial-time algorithm can distinguish these two random graphs with probability $\gg k^2 / n$ \emph{if and only if} the planted clique conjecture holds.The equivalence among search versions identifies the first one-way function that admits a polynomial-time security-preserving self-reduction from exponentially weak to strong one-way functions. These results reveal a detection-recovery gap in success probabilities for the planted clique problem. We also present another equivalence between the existence of a refutation algorithm for the planted clique problem and an average-case polynomial-time algorithm for the $k$-clique problem with respect to the Erd\H{o}s--R\'enyi random graph.

ISSN 1433-8092 | Imprint