Columbia / Courant Joint Probability Seminar

Columbia University, Wednesday April 19, 2017



4:00-4:30 pm
Coffee and tea (Room 508)
4:30-5:30 pm
Jean Bertoin (departmental colloquium) [TBA]
5:45-6:30 pm
Zhou Fan [Probabilistic analysis of a semidefinite program on sparse Erdos-Renyi graphs]
6:30-7:15 pm
Cyril Labbé [TBA]

Practical Information
The talks will take place at Columbia University Mathematics building in Room 520, on April 19, 2017. No registration necessary. However, if you would like to attend the group dinner after the talks, please RSVP.

Directions to Columbia.

For further information, please contact the organizers.

Titles and Abstracts

Jean Bertoin (Zurich)

Abstract: TBA

Zhou Fan (Stanford)
Probabilistic analysis of a semidefinite program on sparse Erdos-Renyi graphs

Abstract: 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.

Cyril Labbé (Paris Dauphine)

Abstract: TBA