Low-degree phase transitions for detecting a planted clique in sublinear time

Jay Mardia, Kabir Aladin Verchand, Alexander S. Wein

We consider the problem of detecting a planted clique of size $k$ in a random graph on $n$ vertices. When the size of the clique exceeds $\Theta (\sqrt{n})$, polynomial-time algorithms f…