Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares

Yash Deshpande
Graduate student, Stanford University
Date: Jan. 22nd, 2016


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


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.