Siu On Chan: Lower Bounds for Extended Formulations
Friday, August 1, 2014 - 12:45pm to 3:45pm
Refreshments:
Pizza at 12:30pm
Location:
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Speaker:
Siu On Chan
Biography:
MSR
Seminar group:
Linear and semidefinite programs can sometimes be rewritten to significantly reduce the number of inequalities in the programs. Such a rewriting is known as an extended formulation. In this talk I will survey recent results in this area, such as lowerbounds for Max-Cut, Max-Clique, and Max-CSPs (but perhaps no time for Perfect Matching). I will discuss the connection of extended formulations to LP and SDP hierarchies, non-negative rank, and common information.
Based mostly on Fiorini–Massar–Pokutta–Tiwary–de Wolf STOC 2012, Braun–Pokutta FOCS 2013, Chan–Lee–Raghavendra–Steurer FOCS 2013, and Lee–Raghavendra–Steurer–Tan CCC 2014.