2013: The year of (nonexistent) extended formulations

2013 has been the year of compact extended formulations (CEF), or rather CEFs that were shown not to exist.

A classical example is the spanning tree polytope (STP). It has exponentially many facets when using the original variables. This may be surprising to some, given that the minimum spanning tree problem is solvable in polynomial time. However, the STP does have a CEF.

One may then wonder, just how powerful are CEFs? Do they exist for every problem? And, if so, can they be constructed efficiently? The obvious answer would be no, because this would imply that P=NP. However, can the limits of CEFs be shown without the assumption that P\neNP?

In a landmark 1991 paper, Yannakakis showed that the traveling salesman polytope has no CEF (under a relatively minor technical assumption).  Just last year, it was finally shown that Yannakakis’ technical assumption is not needed; there is no CEF for the traveling salesman polytope. These papers are fascinating on their own, but are actually useful. Referees can (and should) immediately reject a paper that claims to prove P=NP with a poly-sized traveling salesman LP.

In the last year, (optimal) limits of CEFs have been shown for the clique problem. First, some context is helpful. In 1996, Håstad showed that, for any fixed \epsilon >0 the maximum clique problem cannot be approximated to within a factor of n^{1-\epsilon}, unless NP=ZPP.  Zuckerman later showed the same result under the weaker assumption that P\neNP. What about extended formulations for clique? Just this year, Braverman and Moitra showed the same hardness results hold for CEFs without the assumption that P\neNP.

So far, every problem mentioned so far fits into a nice dichotomy: the polynomial-time solvable problems have CEFs and the NP-hard problems do not. Is this always the case? Can one show that every polynomial-time solvable problem admits a CEF? If so, this would prove that P\neNP.

Alas, no. This year, Rothvoß showed that the perfect matching polytope has no CEF, despite the fact that one can optimize any linear objective over the perfect matching polytope in polynomial time. In fact, he shows that any extended formulation for perfect matching or for the traveling salesman requires 2^{\Omega(n)} entities. The previous best lower bounds for matching and the traveling salesman polytopes were \Omega (n^2) and 2^{\Omega(\sqrt n)}, respectively.

Whether or not the matching polytope has a CEF was a long-standing open question, and Lance Fortnow has justly described Rothvoß’s discovery as the complexity result of the year. But can his result be improved? The best-known upper bound on the extension complexity of the matching polytope is O^* (2^{n/2}). Can Rothvoß’s technique be refined to show a matching lower bound?

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s