The Matching Polytope Has Exponential Extension Complexity

Thomas Rothvoss, UW-Seattle


Date: 2017-11-13
Time: 2pm - 3pm
Location: Room 4258, CSE Building, UC San Diego

Guest Speaker: Thomas Rothvoss, University of Washington Seattle
Assistant Professor, Math and Computer Science

Host: CSE Theory Seminar


UW Seattle professor Thomas Rothvass addresses the matching polytop in the next instalment of the CSE Theory Seminar of the Fall 2017 speaker series.

A popular method in combinatorial optimization is to express polytopes P, which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial. After two decades of standstill, recent years have brought amazing progress in showing lower bounds for the so called extension complexity, which for a polytope P denotes the smallest number of inequalities necessary to describe a higher dimensional polytope Q that can be linearly projected on P.  However, the central question in this field remained wide open: can the perfect matching polytope be written as an LP with polynomially many constraints? We answer this question negatively. In fact, the extension complexity of the perfect matching polytope in a complete n-node graph is 2^Omega(n).


Thomas Rothvoss joined University of Washington Seattle in January 2014 and currently holds a joint position in the Math and CSE departments. Prior to coming to UW, he completed his post-doctoral research at MIT working with Professor Michael Goemans. Rothvoss's research interests are discrete optimization, linear/integer programming and theoretical computer science.