Rounding Moment Based SDP Relaxations by Column Selection

Computer Science/Discrete Mathematics Seminar II
Topic:Rounding Moment Based SDP Relaxations by Column Selection
Speaker:Ali Sinop
Affiliation:Member, School of Mathematics
Date:Tuesday, October 8
Time/Room:10:30am - 12:30pm/S-101
Video Link:https://video.ias.edu/csdm/2013/1008-AliSinop

In this lecture, I will talk about moment based SDP hierarchies (which are duals of SOS relaxations for polynomial optimization) in the context of graph partitioning. The focus will be on a certain way of rounding such hierarchies, whose quality is related to the problem of column based matrix reconstruction. Finally I will describe how to relate this to the spectral or isoperimetric profiles of the underlying constraint graph.