Theory of Computing Seminar

Friday December 5, 2014 12:00 PM

The hidden subgraph problem

Speaker: Andrea Montanari, Stanford
Location: Annenberg 213

Abstract:

I will discuss the problem of finding  a hidden subgraph in an otherwise
random graph. The distinguishing feature of the hidden subgraph is that its average  
degree is higher than the background.  
This problem has applications in a variety of contexts, from network analysis to clustering, 
and is intimately connected to dimensionality reduction and principal component analysis.
I will consider two different regimes:  a sparse graph regime, where the graph 
degree remains bounded as the number of vertices diverges, and 
a dense graph regime, where the average degree is proportional to the number of vertices.
The last setting includes --as a special case-- the hidden clique problem.
I will show that both regimes are characterized by computational and statistical 
phase transitions, and that indeed these phase transitions can be described 
within a unified manner.
[Based on joint work with Yash Deshpande]
 
Series Theory of Computing Seminar Series

Contact: Thomas Vidick vidick@cms.caltech.edu