|Computer Science/Discrete Mathematics Seminar II|
|Topic:||Rounding Moment Based SDP Relaxations by Column Selection|
|Affiliation:||Member, School of Mathematics|
|Date:||Tuesday, October 8|
|Time/Room:||10:30am - 12:30pm/S-101|
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.