Rectangle covers and bounding the extension complexity of the correlation polytope

Abstract

This week we will discuss rectangle covers and their relation to extension complexity. With this combinatorial approach, we will generate lower bounds on the extension complexity of the correlation polytope. This talk largely focuses on the paper “A short proof that the extension complexity of the correlation polytope grows exponentially” by Kaibel and Weltge (2013).