- Series
- Stochastics Seminar
- Time
- Thursday, April 6, 2017 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 006
- Speaker
- Zhou Fan – Stanford University
- Organizer
- Christian Houdré
Spectral algorithms are a powerful method for detecting low-rank structure
in dense random matrices and random graphs. However, in certain problems
involving sparse random graphs with bounded average vertex degree, a naive
spectral analysis of the graph adjacency matrix fails to detect this
structure. In this talk, I will discuss a semidefinite programming (SDP)
approach to address this problem, which may be viewed both as imposing a
delocalization constraint on the maximum eigenvalue problem and as a
natural convex relaxation of minimum graph bisection. I will discuss
probabilistic results that bound the value of this SDP for sparse
Erdos-Renyi random graphs with fixed average vertex degree, as well as an
extension of the lower bound to the two-group stochastic block model. Our
upper bound uses a dual witness construction that is related to the
non-backtracking matrix of the graph. Our lower bounds analyze the behavior
of local algorithms, and in particular imply that such algorithms can
approximately solve the SDP in the Erdos-Renyi setting.
This is joint work with Andrea Montanari.