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.