Time: 1:30pm Tuesday, 23rd February.
Location: SIT 459
Speaker: David Avis, Kyoto University
Title: Extension Complexity
An overview of extension complexity up to Rothvoss’ result that the matching polytope has exponential extension complexity, then two avenues to move forward. (a) H-free extension complexity which allows certain ‘easy’ constraints to be ignored. (b) An explicit construction of polynomial size polytopes for matching and other problems in P.
(Joint work with D. Bremner, H. Tiwary, and O. Watanabe)