Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
Friday, January 22, 2016 - 1:00pm to 2:00pm
Packard 202
Yash Deshpande (Stanford)
Abstract / Description: 

Characterizing the computational complexity 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 dramatically alter the inference ability. 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 characterizing 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 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.


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Kartik Venkat. To suggest speakers, please contact any of the students.


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.