We study the planted clique problem in which a clique of size k is planted in an Erdos-R\'enyi graph of size n and one wants to recover this planted clique. For k=\Omega(n), polynomial time algorithms can find the planted clique. The fastest such algorithms run in time linear O(n^2) (or nearly linear) in the size of the input [FR10,DGGP14,DM15a]. In this work, we develop sublinear time algorithms that find the planted clique when k=\omega(n \log \log n). Our algorithms can recover the clique in time O\left(n+(n{k})^{3}\right)=O\left(n^{3{2}}\right) when k=\Omega(n\log n), and in time O\left(n^2/\left(\frac{k^2{24n}\right)}\right) for \omega(n\log \log n)=k=o(n\log{n}). An {\Omega}(n) running time lower bound for the planted clique recovery problem follows easily from the results of [RS19] and therefore our recovery algorithms are optimal whenever k = \Omega(n^{2{3}}). As the lower bound of [RS19] builds on purely information theoretic arguments, it cannot provide a detection lower bound stronger than \Omega(\frac{n^2}{k^2}). Since our algorithms for k = \Omega(\sqrt{n \log n}) run in time \widetilde{O}\left(\frac{n^3}{k^3} + n\right), we show stronger lower bounds based on computational hardness assumptions. With a slightly different notion of the planted clique problem we show that the Planted Clique Conjecture implies the following. A natural family of non-adaptive algorithms---which includes our algorithms for clique detection---cannot reliably solve the planted clique detection problem in time O\left( \frac{n^{3-\delta}}{k^3}\right) for any constant \delta>0. Thus we provide evidence that if detecting small cliques is hard, it is also likely that detecting large cliques is not \textit{too} easy.
We study the planted clique problem in which a clique of size k is planted in an Erdos-R\'enyi graph of size n and one wants to recover this planted clique. For k=\Omega(n), polynomial time algorithms can find the planted clique. The fastest such algorithms run in time linear O(n^2) (or nearly linear) in the size of the input [FR10,DGGP14,DM15a]. In this work, we initiate the development of sublinear time algorithms that find the planted clique when k=\omega(n \log \log n). Our algorithms can recover the clique in time O\left(n+(n{k})^{3}\right)=O\left(n^{3{2}}\right) when k=\Omega(n\log n), and in time O\left(n^2/\left(\frac{k^2{24n}\right)}\right) for \omega(n\log \log n)=k=o(n\log{n}). An {\Omega}(n) running time lower bound for the planted clique recovery problem follows easily from the results of [RS19] and therefore our recovery algorithms are optimal whenever k = \Omega(n^{2{3}}). As the lower bound of [RS19] builds on purely information theoretic arguments, it cannot provide a detection lower bound stronger than \Omega(\frac{n^2}{k^2}). Since our algorithms for k = \Omega(\sqrt{n \log n}) run in time \widetilde{O}\left(\frac{n^3}{k^3} + n\right), we show stronger lower bounds based on computational hardness assumptions. With a slightly different notion of the planted clique problem we show that the Planted Clique Conjecture implies the following. A natural family of non-adaptive algorithms---which includes our algorithms for clique detection---cannot reliably solve the planted clique detection problem in time O\left( \frac{n^{3-\delta}}{k^3}\right) for any constant \delta>0. Thus we provide evidence that if detecting small cliques is hard, it is also likely that detecting large cliques is not \textit{too} easy.
R
develop
initiate the development of