Sum of squares Lower bounds for Hidden Clique and Hidden Submatrix Problems

Mon, Sep. 21

3-4PM

400 Cory

3-4PM

400 Cory

Characterizing the computational difficulty of statistical inference problems
is an outstanding open problem. This is gaining increasing importance given
the ubiquity of large scale data analysis and algorithms in application domains
as diverse as genomics, healthcare, finance and social sciences.

The hidden clique problem is a prototypical example of an inference problem wherein computational constraints are more onerous in comparison to the usual statistical or information-theoretic constraints. The hidden clique problem posits to find a "hidden" or "planted" clique (a densely connected set of vertices) within an otherwise random Erdos-Renyi graph. Unfortunately, standard reduction tools from theoretical computer science to demonstrate hardness fail to capture statistical nature of the hidden clique problem.

I will describe a framework based on the powerful Sum-of-Squares (SOS) technique for understanding computational difficulty in the hidden clique and other related problems. The analysis of the SOS algorithms requires controlling the spectra of random matrices of a fairly non-standard type. I will describe a set of results that represent the state-of-the-art in proving lower bounds for the hidden clique and related problems.

This is based on joint work with Andrea Montanari.

Bio: Yash Deshpande received a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay in 2011. Since 2011, he is a Ph.D candidate at the Electrical Engineering department in Stanford, where he is advised by Prof. Andrea Montanari. His research interests are in statistical inference, graphical models, message passing algorithms and applied probability.

The hidden clique problem is a prototypical example of an inference problem wherein computational constraints are more onerous in comparison to the usual statistical or information-theoretic constraints. The hidden clique problem posits to find a "hidden" or "planted" clique (a densely connected set of vertices) within an otherwise random Erdos-Renyi graph. Unfortunately, standard reduction tools from theoretical computer science to demonstrate hardness fail to capture statistical nature of the hidden clique problem.

I will describe a framework based on the powerful Sum-of-Squares (SOS) technique for understanding computational difficulty in the hidden clique and other related problems. The analysis of the SOS algorithms requires controlling the spectra of random matrices of a fairly non-standard type. I will describe a set of results that represent the state-of-the-art in proving lower bounds for the hidden clique and related problems.

This is based on joint work with Andrea Montanari.

Bio: Yash Deshpande received a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay in 2011. Since 2011, he is a Ph.D candidate at the Electrical Engineering department in Stanford, where he is advised by Prof. Andrea Montanari. His research interests are in statistical inference, graphical models, message passing algorithms and applied probability.

UC Berkeley Networking

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016