Extension Complexity
Last week I gave an introductory lecture on extension complexity for my communication complexity reading group. It is a fascinating topic, discussing if a polytope with exponentially many facets might be described as a linear projection from a higher dimensional polytope with polynomially many facets. Specifically, the extension complexity is defined as xc(P) := min{# facets of Q : Q projects to P}. A classical example of this would be the permutohedron with dimension N; it has 2^N - 2 facets, but there is a polytope in dimension N^2 + N with O(N^2) facets which projects to the permutohedron. I covered this example, as well as Yannakakis' theorem, which shows an equivalence between extension complexity and nonnegative rank of a certain matrix. I also highlight a connection with communication complexity, which will be expanded upon in the upcoming semester. I hope to give more in-depth lectures, with the intent of covering Rothvoss' 2017 result on exponential lower bounds for