Theory of Computing Seminar
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]
For more information, please contact Thomas Vidick by email at [email protected].
Event Series
Theory of Computing Seminar Series