# 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.

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:

34L15

Keywords: