TCS in the Big Apple – STOC 2014 Recaps (Part 1)

courtesy of frontpagemag.comAh, 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. Semidefinite 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 PTSP 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 PTSP takes exponential time! Instead, people would like to optimize over another polytope in higher dimension QTSP that projects down to PTSP (such a QTSP would be called a linear extension of PTSP) except now QTSP 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 QTSP of PTSP 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 PPM (the convex hull of all perfect matchings in K_n)? This is interesting question for a number of reasons: this polytope, like PTSP, has an exponential number of facets. However, unlike the TSP polytope, optimizing linear objective functions over PPM 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 PPM, 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 P, \mathrm{xc}(P) = \mathrm{rank}_{+}(S_P), where the left-hand side denotes the extension complexity of P [2], and the right-hand side denotes the non-negative rank of the slack matrix of P [3]. Now, instead of worrying about every possible linear extension of P, we “only” have to focus our attention on the non-negative rank of S_P. 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 S be an arbitrary non-negative m\times n matrix; and W be an arbitrary matrix of the same dimensions (not necessarily non-negative). Then \mathrm{rank}_+(S) \geq \langle W, S \rangle/ (\|S \|_\infty \alpha_W), where  \langle W, S \rangle is the Frobenius inner product between W and S, \|S \|_\infty is the largest-magnitude entry of S, and \alpha_W := \max \{ \langle W, R \rangle : R \in \{0,1\}^{m \times n}\text{ is rank 1} \}. Intuitively, in order to show that the non-negative rank of S is large, you want to exhibit a matrix W (a “hyperplane”) that has large correlation with S, but has small correlation with any rectangle R. Rothvoss presents such a hyperlane W that proves the matching polytope has exponential extension complexity; the hard part is showing that \langle W, R \rangle \leq 2^{-\Omega(n)} for all rectangles R. To do so, Rothvoss follows a similar strategy to Razborov’s proof of the \Omega(n) 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] \mathrm{xc}(P) is defined to be the minimum number of facets of any polytope that linearly projects to P.

[3] Let S be a non-negative matrix of size m\times n. Then \mathrm{rank}_+(S) = k if there exists a factorization S = TU where T and U are non-negative matrices, and T and U have dimensions m\times k and k\times n, respectively. Let P = \{x : Ax \leq b \} is a polytope defined by m inequalities, with vertices v_1,\ldots,v_n. Then the (i,j)th entry of the slack matrix S_P of P is defined to be b_j - A_j v_i, with A_j the jth row of A.

2 thoughts on “TCS in the Big Apple – STOC 2014 Recaps (Part 1)

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

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s