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
- Sam Buss and Ryan Williams for their limits on the time-space tradeoffs for Satisfiability.
- Paul Beam, Christopher Beck and Russell Impagliazzo for Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space
- Tsuyoshi Ito and Thomas Vidick: MIP with entangled provers still contains NEXP
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şcu, Ernst 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.
What happened to the idea of making articles freely available? The links you provide go to ACM or IEEE.
ReplyDeleteThe 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.
ReplyDeleteLets see what happens in next year's STOC, FOCS, CCC, ICALP or FSTTCS.
Would it be possible to compile the list the Complexity Theory results
ReplyDeleteof 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.
"any LP formulation of TSP requires an exponential sized LP"
ReplyDeleteThis 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?
There are many ways to resolve the dilema you posed. Here's one.
DeleteThe 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.
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
Delete@anon 12:53: Logspace reductions are of course also polynomial time reductions.
DeleteHello! Thank you very much for the very interesting post and tips, I enjoyed reading this. I learned a lot of interesting and educational things. I will definitely put your advice into practice.
ReplyDeleteI also tried how it works and I liked playing online casino game bonuses https://jennycasino.com/ and slot machines.