Abstract
In this tutorial we will cover the recent progress on lower bounds on the size of linear programs and semidefinite programs for combinatorial optimization problems. We will present the definition and motivation of extension complexity and the relation to communication complexity. Then we will discuss the lower bound of Fiorini et al for the TSP and correlation polytope. We will also review SDP extension complexity with related concept such as the SDP rank of matrices. Finally, we will discuss lower bounds based on Fourier-methods by CLRS and LRS for both the LP model and the SDP model.
The first session of this mini course will take place on Wednesday, August 23 from 1:30 - 2:30 PM; the second session of this mini course will take place on Wednesday, August 23 from 3:00 - 4:00 PM; the third session of this mini course will take place on Thursday, August 24 from 3:00 - 4:00 PM; and the fourth session of this mini course will take place on Thursday, August 24 from 4:30 - 5:30 PM.