The Catalan Grenade

 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 boun...

 Since the Winter 2020 semester at McGill, I've helped run a Communication Complexity reading group attended by undergraduate and graduate students. Recently, I became particularly excited by the Number-on-the-Forehead model, and gave a talk on it in the reading group.  The idea is quite simple. For 2 player communication, imagine that Alice's input is on top of Bob's forehead, making it easy for Alice to see but impossible for Bob to see. Likewise, Bob's input is on Alice's forehead.  This generalizes to k-player problems where k people stand in a circle, each with a card on their forehead indicating some information that is viewable to everyone but the forehead owner.  If this still doesn't make sense, think of this scene from The Office.  Here are the  lecture notes  I wrote for the talk. I cover basic definitions, Behrend's bound and it's application to the Exactly-N problem, and Ramsey Theoretic lower bounds on cylinders.  As I liked this to...

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 ...