Theory of Computing Seminar
Friday December 5, 2014 12:00 PM
The hidden subgraph problem
Speaker: Andrea Montanari, Stanford
Location: Annenberg 213
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 firstname.lastname@example.org