Finding planted cliques using gradient descent

Reza Gheissari, Aukosh Jagannath, Yiming Xu

The planted clique problem is a paradigmatic model of statistical-to-computational gaps: the planted clique is information-theoretically detectable if its size $k\ge 2{\log }_{2}n$ but…