Uncertainty Seminar

Planted Gaussian problem: beating the spectral bound

Spectral methods can find a planted clique of size c\sqrt n in a random graph.  In spite of some effort, this is the best we know so far.  Here, for a different natural problem (of a similar flavor), we show that we can do better than spectral methods.  Given an n times n matrix with i.i.d. N(0,1) entries everywhere except for a planted k by k submatrix which has N(0,\sigma^2) entries, we show that if \sigma^2 > 2, then we can find a planted clique of size o(\sqrt n).  We also show that if \sigma^2 \leq 2, no poly time statistical algorithm can find the planted part if it is o(\sqrt n) sized.  The algorithm as well as the lower bound are based on the chi-squared distance between the planted and ground densities. Some extensions will also be discussed.
This is joint work with Santosh Vempala.