Siu On Chan: Lower Bounds for Extended Formulations

Friday, August 1, 2014 - 12:45pm to 3:45pm
Pizza at 12:30pm
MSR New England (Barton room on the 1st floor of One Memorial Drive building)
Siu On Chan

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.