The following probabilistic model of a graph on $n$ labeled vertices is considered. First choose a random graph $G(n,1/2)$ and then choose randomly a subset $Q$ of vertices of size $k$ and force it to be a clique by joining every pair of vertices of $Q$ by an edge. The problem is to give a polynomial time algorithm for finding this hidden clique almost surely for various values of $k$. This question was posed independently, in various variants, by Jerrum and by Ku\v{c}era. In this talk I will present an efficient algorithm for all $k > cn^{0.5}$, for any fixed $c>0$, thus improving the trivial case $k > c n^{0.5} (\log n)^{0.5}$. The algorithm is based on the spectral properties of the graph.

This is a joint work with Noga Alon and Benny Sudakov.