### Michael Krivelevich

### Institute for Advanced Study

### Finding a Large Hidden Clique in a Random Graph

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.