ECCC-Report TR24-058https://eccc.weizmann.ac.il/report/2024/058Comments and Revisions published for TR24-058en-usSun, 31 Mar 2024 17:01:34 +0300
Paper TR24-058
| Planted Clique Conjectures Are Equivalent |
Shuichi Hirahara,
Nobutaka Shimizu
https://eccc.weizmann.ac.il/report/2024/058 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.Sun, 31 Mar 2024 17:01:34 +0300https://eccc.weizmann.ac.il/report/2024/058