Finding Hidden Cliques in Linear Time with High Probability

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

We are given a graph $G$ with $n$ vertices, where a random subset of $k$ vertices has been made into a clique, and the remaining edges are chosen independently with probability $\t…