[Computational Complexity] Unique Games Redux
- With spring quarter arriving, I will take a break from book writing on P v. NP and come back to blogging. I hit my goal of getting past the point of no return (about three draft chapters out of ten) but writing a book is a slow process.
I've been hearing a bit of buzz about a new algorithm from Arora, Barak and Steurer for unique games that I first saw in Luca's blog: Given a unique game where 1-δ fraction of the edges can be satisfied, you can in time 2npoly(1/δ) find a coloring that satisfies a constant fraction of edges.
Does this kill the unique games conjecture, that the unique games problem is NP-hard? Not yet. For every ε>0, there are NP-complete sets sitting in time 2nε. It's possible that there is some reduction from SAT to unique-games will have the property that to get a smaller δ requires an algorithm with a running time whose polynomial depends on δ.
But does it give evidence that unique games may now be false (right after Khot won the Waterman award)? Any improvement in the Arora-Barak-Steurer algorithm would yield a subexponential-time algorithm for NP if the unique games conjecture holds.
But in the end it could go the other way. If no one improves on the ABS algorithm in the next year or so, it will seem like we've hit a barrier right at the edge of where the UGC could still be true. Which will make us think that UGC could be true again and after a while, ought to be true.
As Nietzsche might have said, what doesn't kill the unique games conjecture will only make it stronger.
Posted By Lance to Computational Complexity at 3/19/2010 09:27:00 AM