C&O Reading Group - Jacob Skitsko

Monday, May 15, 2023 1:00 pm - 1:00 pm EDT (GMT -04:00)

Title: The matching polytope has exponential extension complexity

Speaker: Jacob Skitsko
Affiliation: University of Waterloo
Location: MC 6029

Abstract: This Friday we will build off of some previous results by looking at the paper “The matching polytope has exponential extension complexity” by Thomas Rothvoss! At the beginning of the semester, we saw that the matching (and TSP) polytopes cannot be expressed by a polynomial sized symmetric LP. But what about non-symmetric LPs? More recently we saw that the extension complexity of the correlation polytope grows exponentially, by using a lower bound on the rectangle covering number. But unfortunately, the rectangle covering number doesnt immediately give us exponential extension complexity for the matching polytope. Nonetheless, we will squint very hard and see that the matching (and TSP) polytope does in fact have exponential extension complexity.