Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 31, 2019, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Volker Kaibel (OVGU)
The extension complexity of a polytope is the smallest number of facets of any polyhedron of which it is a linear projection. In a seminal paper Fiorini, de Wolf, Massar, Pokutta, and Tiwary (2012) established an exponential lower bound on the extension complexity of the correlation polytope, implying corresponding lower bounds for several other polytopes such as the traveling salesman polytope. In this talk we present a very simple and hopefully pleasing proof that establishes the currently best known lower bound (3/2)^n on the extension complexity of the correlation polytope for n variables. The talk is based on joint work with Stefan Weltge.
Automatic MiSe System Software Version 1.4803M | admin login