This work is licensed under a
Creative Commons License.
|
Friday, March 19, 2010
Unique Games Redux
Posted by Lance
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(δ) 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.
9:27 AM
# 9 comments
-
you wrote that an instance with 1-delta satisfiable clauses can be solved in
2^{n^{poly{1/delta}}} time.
Shouldn't it be:
s^{n^{poly(delta)}} time?
-
oops, I meant:
2^{n^{poly(delta)}} time.
-
Right. Fixed.
-
Even if Unique Games is not NP-complete, that does not kill all hope of its utility. As long as Unique Games is not in P, many of its consequences still essentially hold, although in a somewhat weakened form.
-
Someone once to told that good conjectures are not those that lead to answers and proofs, but those which result in interesting developments (even when they are false, Hilbert program is an excellent example), and UGC does satisfy the condition.
-
Lots of people working on something does not make that thing "interesting".
The whole story and hype surrounding the UGC is a huge embarassment for TCS.
Even if the UGC is true.
Lance Fortnow's last line really summed it up beautifully.
-
> The whole story and hype
> surrounding the UGC is a huge
> embarassment for TCS.
Why would it be an embarassment?
I really like the UGC and I don't see what's so bad about it.
-
Lots of people working on something does not make that thing "interesting".
It doesn't to you I am sure. But socially, to the community, I think that is a fairly accurate definition of interesting. Please enlighten us with a better one that applies not just in hindsight, if you don't like this one.
-
Please enlighten us with a better one that applies not just in hindsight, if you don't like this one.
If we knew how to define what is interesting, it would be an awful lot easier to make decisions about conference submissions and grant applications. What lots of people are working on is a decent first approximation to what's interesting, but it's hardly the end of the story, and it's perfectly reasonable to disagree in either direction.
Links to this post:
Weblog Home
Archives
