Sum of Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Thursday, May 21, 2015 - 3:30pm - 4:20pm
Keller 3-180
Yash Deshpande (Stanford University)
Given a large random matrix A, we consider the following testing problem. Under the
null hypothesis, every entry of A is generated i.i.d. from a distribution P_0. Under the alternative H_1, there is a submatrix indexed by Q, a subset of {1, 2, ... n} such that
the entries of A in Q X Q are generated instead according to a different law P_1, while
the other entries are as in the null.

A special case of this problem is the hidden clique problem, which posits to find a clique
in an otherwise random Erdos-Renyi graph. Although, information-theoretically, the testing
problem is solvable via brute force search when Q = O(log n), no known polynomial time
algorithm is known to even approach this threshold. I will discuss a powerful class of
semidefinite programs, known as the Sum of Squares Hierarchy specialized to this
problem, and establish computational lower bounds for the first level of the hierarchy
that goes beyond vanilla spectral methods.

The analysis involves controlling the eigenvalues of some non-standard ensembles of
random matrices via the trace method.

This is joint work with Andrea Montanari.
MSC Code: