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 the matching polytope.

Here are the lecture notes if you are interested! Credit to Rothvoss' talk for several examples used.


Popular posts from this blog

Derandomization of BPP Using Hitting Set Generators

Number-on-the-Forehead Communication Complexity

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication