Ah, summertime. For many NotSoGITCSers, it means no classes, warm weather, ample research time… and a trip to STOC. This year the conference was held in New York City, only four hours away from Cambridge via sketchy Chinatown tour bus. Continuing in the great tradition of conference blogging by TCS blogs (see here, and here), NotSoGITCS will share some of our favorite papers from the conference. I’ll start this off with my recap on Rothvoss’s paper on extension complexity. Over the next few posts, we’ll hear from Clément Canonne and Gautam Kamath on Efficient Distribution Estimation, Pritish Kamath on the latest results in algebraic circuit complexity, Justin Holmgren on indistinguishability obfuscation, and Sunoo Park on coin flipping!

Henry Yuen on **The matching polytope has exponential extension complexity**, by Thomas Rothvoss

The Best Paper award for this year’s STOC went to this paper, which is another milestone result in the recent flurry of activity in *lower bounds for extension complexity of combinatorial problems*. This area represents a fruitful “meeting in the middle” between complexity theory and algorithms. Although a proof of P ≠ NP — a conjecture about the limitation of *all* polynomial time algorithms — seems astronomically distant, we can instead shoot for a closer goal: show that polynomial time algorithms we know of *now* cannot solve NP-complete problems. The area of extension complexity is about understanding the limitations of some of the finest weapons in our polynomial-time toolbox: LP and SDP solvers. As many of you know, these algorithms are tremendously powerful and versatile, in both theory and practice alike.

A couple years ago, STOC 2012 (also held in New York!) saw the breakthrough result of Fiorini, et al. titled *Linear vs. Semideﬁnite Extended Formulations: Exponential Separation and Strong Lower Bounds*. This paper showed that while powerful, LP solvers cannot *naturally* solve NP-complete problems in polynomial time. What do I mean by naturally solve? Let’s take the Traveling Salesman Problem for a moment (which was the subject of the aforementioned paper). One way to try to solve TSP on an *n*-city instance using linear programming is to try to optimize over the polytope P_{TSP} where each vertex corresponds to a tour of the complete graph on *n* nodes. Turns out, this polytope has exponentially many facets, and so is a rather unwieldy object to deal with — simply *writing* down a system of linear inequalities defining P_{TSP} takes exponential time! Instead, people would like to optimize over another polytope in higher dimension Q_{TSP} that *projects* down to P_{TSP} (such a Q_{TSP} would be called a *linear extension* of P_{TSP}) except now Q_{TSP} has a polynomial number of facets. Does such a succinct linear extension exist? If so, that would imply P = NP! The Fiorini, et al. paper showed that one can’t solve the Traveling Salesman Problem this way: the TSP polytope has *exponential extension complexity* — meaning that any linear extension of Q_{TSP} of P_{TSP} necessarily has exponentially many facets ^{[1]}.

In a sense, one shouldn’t be too surprised by this result: after all, we all *know* that P ≠ NP, so *of course* the TSP polytope has exponential extension complexity. But we’ve learned more than just that LP solvers can’t solve NP-complete problems: we’ve gained some insight into the *why*. However, after the Fiorini et al. result, the natural question remained: is this exponential complexity of polytopes about NP-hardness, or is it something else? In particular, what is the extension complexity of the *perfect matching polytope* P_{PM} (the convex hull of all perfect matchings in )? This is interesting question for a number of reasons: this polytope, like P_{TSP}, has an exponential number of facets. However, *unlike* the TSP polytope, optimizing linear objective functions over P_{PM} is actually polynomial-time solvable! This is due to the seminal work of Jack Edmonds, who, in the 1960’s, effectively brought the notion of “polynomial time computability” into the (computer science) public consciousness by demonstrating that the maximum matching problem admits an efficient solution.

As you might have guessed from the title, Thomas Rothvoss showed that actually the matching polytope cannot be described as the projection of a polynomially-faceted polytope! So, while we have LP-based algorithms for optimizing over P_{PM}, these algorithms must nontrivially rely on the structure of the matching problem, and *cannot* be expressed as generically optimizing over some succinct linear extension. I’ll say a few words about how he shows this. To lower bound the extension complexity of a polytope, one starts by leveraging the Yannakakis’s Factorization Theorem, proved in his 1991 paper that started the whole area of extension complexity. His theorem says that, for a polytope , , where the left-hand side denotes the extension complexity of ^{[2]}, and the right-hand side denotes the *non-negative rank* of the *slack matrix* of ^{[3]}. Now, instead of worrying about every possible linear extension of , we “only” have to focus our attention on the non-negative rank of . It turns out that fortuitously, we have techniques of lower bounding the non-negative rank of matrices from communication complexity (a connection that was also pointed out by Yannakakis). Roughly speaking, communication complexity tells us that the non-negative rank of a matrix is high if the matrix cannot be “described” as a small collection of combinatorial rectangles.

This idea is captured in what Rothvoss calls the “Hyperplane separation lower bound”: let be an arbitrary non-negative matrix; and be an arbitrary matrix of the same dimensions (not necessarily non-negative). Then , where is the Frobenius inner product between and , is the largest-magnitude entry of , and . Intuitively, in order to show that the non-negative rank of is large, you want to exhibit a matrix (a “hyperplane”) that has large correlation with , but has small correlation with any rectangle . Rothvoss presents such a hyperlane that proves the matching polytope has exponential extension complexity; the hard part is showing that for all rectangles . To do so, Rothvoss follows a similar strategy to Razborov’s proof of the lower bound on the randomized communication complexity of DISJOINTNESS, with substantial modifications to fit the matching problem.

There are a number of reasons why I like these papers in extension complexity: they’re concrete, solid steps towards the dream of proving P ≠ NP. They’re short and elegantly written: the Fiorini, et al. paper is 24 pages; the Rothvoss paper is less than 20. They also demonstrate the unity of theoretical computer science: drawing upon ideas from algorithms, combinatorics, communication complexity, and even quantum information.

-Henry Yuen

[1] Well, now we know that these guys couldn’t have used a succinct extended formulation.

[2] is defined to be the minimum number of facets of any polytope that linearly projects to .

[3] Let be a non-negative matrix of size . Then if there exists a factorization where and are non-negative matrices, and and have dimensions and , respectively. Let is a polytope defined by inequalities, with vertices . Then the th entry of the slack matrix of is defined to be , with the th row of .

Nice article! I am wondering — what do you think is the high-level, “moral” message of this paper? It seems (at first glance) to be saying that LP solvers, however powerful, do not always/systematically yield a way to *generically* solve problems, even in P — and that even in good cases, there can be a lot more insight and work required that just pressing a button and getting an efficient LP approach. Is that how one should interpret it, or I am off?

Yeah, I would agree that’s one moral message of the result. Like I mentioned in my post, the matching problem really put the concept of “polynomial time” on the map, because, at the time, it wasn’t clear at all how one could avoid exhaustive search to solve the problem. But Edmonds then showed, lo and behold, here’s a solution that’s much faster than brute force, and it makes a

difference. I would say that Rothvoss’s result justifies Edmonds’s choice of the matching problem to illustrate the non-triviality of P, 50 years later: now we know that matching isn’t in P only because one can just crank the matching polytope through an off-the-shelf LP solver. Rather, some real combinatorial cleverness, tailored to match the matching problem, is required.Actually, I was just re-reading Edmonds’s justification for the notion of polynomial time (see “Digression” in http://www.disco.ethz.ch/lectures/fs12/seminar/paper/Tobias/2.pdf). It’s striking how lucid and clear Edmonds understands the importance of efficient computability, as well as the value of asymptotic analysis. He also mentions the question of whether graph isomorphism is in P! I highly recommend reading these few paragraphs to anybody.