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.

Comments

Post a Comment

Popular posts from this blog

Learning Bounded Arithmetic -- A Guide from a Novice

-
Bounded Arithmetic is a field of mathematical logic which, very roughly, studies subtheories of Peano Arithmetic that "correspond" with reasoning associated with computational complexity classes or propositional proof systems. Correspond here can mean multiple things, but the two most common interpretations would be the prized Witnessing Theorems or Paris-Wilkies Propositional Translations. At the Simons Institute program for Meta Complexity this winter, many attendants (including myself) wished to learn bounded arithmetic due to its increasing appearances and connections with other areas of complexity. Marco Carmosino, Oliver Korten, and Jan Pich organized a bounded arithmetic reading group to go through many elementary and recent works in bounded arithmetic, with a preference towards those results relating to meta complexity. However, with the creation of the reading group, a running joke was spawned: " I won't define this bounded arithmetic theory " Every we...
Read more

Extension Complexity Part II - Classifying Nonnegative Rank by Randomized Communication

-
A classical result from Yannakakis states that $$\text{xc}(P) = \text{rank}_+(S),$$ where \(P\) is a polytope with slack matrix \(S\). Yannakakis further showed that with nondeterministic communication complexity, one can give a lower bound for the nonnegative rank. This lower bound is sufficient to prove that some polytopes, like the correlation polytope, have exponential extension complexity. However, it fails for many other examples.  In a 2013 paper, "Extended formulations, nonnegative factorizations, and randomized communication protocols," by Faenza, Fiorini, Grappe, and Tiwary, they show that a model of randomized communication complexity can not only lower bound nonnegative rank, but exactly characterize it.  In my communication complexity reading group, I gave a talk presenting this paper and its results. The proofs are extremely elegant and simple, making for a very enjoyable read.  For those interested, here is a link to my lecture notes! 
Read more

Google Summer of Code 2020: D-Complete and Mobile Posets

-
In this post, I thought I'd overview the work of  my first paper , which has just recently been accepted to SIDMA.  In order theory, a linear extension of a partially ordered set P is a totally ordered set L which respects the original ordering P. Many famous problems can be converted into counting the number of linear extensions. For example, the number of standard Young tableaux of a given shape is equivalent to the number of linear extensions of a poset with the same shape. Unfortunately, it is #P-complete in general to count linear extensions (even for posets of height 2!). However, there are famous classes of posets like Young diagrams (or more generally, d-complete posets), which have efficient computation. In our paper, we presented a new class of posets called mobiles that have determinant formulas for counting linear extensions and generalize d-complete posets and ribbon posets. Since this past summer converted me into a shut-in, I decided to spend some of that extra ...
Read more