Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Montanari speaks tomorrow 4PM in Applied Math Seminar

Tim Roughgarden tim at
Tue Dec 1 09:31:37 PST 2015

---------- Forwarded message ----------
From: Andrea Montanari <montanar at>
Date: Tue, Dec 1, 2015 at 8:54 AM
Subject: Seminar
To: "tim at" <tim at>

Hi Tim,

I am giving this seminar in applied math. Perhaps some people in
CS might be interested.

Wednesday, December 2, 4pm: Applied Math Seminar, Sloan Math Center Room 384H

Andrea Montanari,  Stanford Statistics and Electrical Engineering
"Phase transitions in semidefinite relaxations"

Abstract: Statistical inference problems arising within signal
processing, data mining, and machine learning naturally give rise to
hard combinatorial optimization problems. These problems become
intractable when the dimensionality of the data is large, as is often
the case for modern datasets. A popular idea is to construct convex
relaxations of these combinatorial problems, which can be solved
efficiently for large scale datasets. Semidefinite programming (SDP)
relaxations are among the most powerful methods in this family, and
are surprisingly well-suited for a broad range of problems where data
take the form of matrices or graphs. It has been observed several
times that, when the `statistical noise' is small enough, SDP
relaxations correctly detect the underlying combinatorial structures.
I will present a few asymptotically exact predictions for the
`detection thresholds' of SDP relaxations, with applications to
synchronization and community detection.
[Based on Joint work with Adel Javanmard, Federico Ricci-Tersenghi and
Subhabrata Sen]

More information about the theory-seminar mailing list