Thursday, December 27, 2012

2012 Complexity Year in Review

As we turn our thoughts from Turing to Erdős, a look back at the complexity year that was. Written with help from co-blogger Bill Gasarch.

The complexity result of the year goes to Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf for their paper Linear vs Semidefinte Extended Formualtions: Exponential Separation and Strong Lower Bounds (ArXiv version). It is easy to show that TSP can be expressed as an exponentially sized Linear Program (LP). In 1987 Swart tried to show that TSP could be solved with a poly sized LP. While his attempt was not successful it did inspire Yannakakis to look at the issue of how large an LP for TSP has to be.He showed in 1988 that any symmetric LP for TSP had to be exponential size. (Swart had used symmetric LP's).

What about assymetric LP's? This has been open UNTIL NOW! The paper above proves that any LP formulation of TSP requires an exponential sized LP. They use communication complexity and techniques that were inspired by quantum computing.

Runners Up
And don't forget the solution to Bill's 17x17 problem.

News and trends: The new Simons Institute for the Theory of Computing at Berkeley, the great exodus of Yahoo! researchers mostly to Google and Microsoft, the near death of Florida computer science (anyone want to be chair?), and the rise of the MOOCs. 

We remember Dick de Bruijn, Tom Cover, Mihai PătraşcuErnst Specker and David Waltz, not to mention Neil Armstrong and Ray Bradbury

Thanks to our guest posters Bernard Chazelle, Yoav Freund, Andrew Goldberg, Mohammad Taghi Hajiaghayi, William Heisel, Lane Hemaspaandra, John Purtilo, Janos Simon and Vijay Vazirani.

Enjoy 2013 and remember that when living in a complex world, best to keep it simple. And try not to fall off that fiscal cliff.


  1. What happened to the idea of making articles freely available? The links you provide go to ACM or IEEE.

  2. The paper entitled 'Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds' is really a seminal paper and I personally think that the paper somehow holds a key to establish tight hardness of approximation result for some combinatorial optimization problems, including the metric TSP which is undoubtedly one of the best open research problems. Prof. Buss and Prof. Williams's result on satisfiability is also great in its own right.
    Lets see what happens in next year's STOC, FOCS, CCC, ICALP or FSTTCS.

  3. Would it be possible to compile the list the Complexity Theory results
    of the year for the past decade (or even perhaps the past two decades)?

    This might be useful for researchers outside the area.

    Many thanks beforehand.

  4. "any LP formulation of TSP requires an exponential sized LP"
    This cannot be what was proved. LP is P-complete, so a proof of the above statement (reasonably formalized) would appear to imply P neq NP. Can someone explain what was really proved?

    1. There are many ways to resolve the dilema you posed. Here's one.

      The LP formulations for TSP in the paper are required to project exactly to the TSP polytope. This is a bit weaker than saying "any LP formulation of TSP requires an exponential sized LP". Essentially what it means is that you can't have a small polytope such that optimizing over it always gives you a solution for TSP for arbitrary cost-functions (You have to fix the polytope once and for all and it should work for every cost function).

      Nevertheless, since "formulating TSP as an LP" *usually* is done by giving an LP whose associated polyhedral region projects exactly to the TSP polytope and a blog entry probably couldn't do justice to the fine print without alienating non-experts, quite often you'd see the above statement.

      Hope that helps.

    2. P-completeness is a space reduction, not a time reduction and hence LP not being able to solve TSP does not imply there doesn't exist a polynomial time algorithm to solve TSP. Hence the result does not imply P \neq NP

    3. @anon 12:53: Logspace reductions are of course also polynomial time reductions.