Improved polynomial-time algorithms for detecting and recovering planted $\Theta (\sqrt{n})$-cliques

Dmitriy Kunisky, Songtao Mao

In the planted clique problem, one observes either an Erdős--Rényi graph on $n$ vertices or such a graph with a clique added to $k=k(n)$ vertices, and seeks to detect or recover…