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 2^{npoly(δ)}
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 2^{nε}. 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.

you wrote that an instance with 1-delta satisfiable clauses can be solved in

ReplyDelete2^{n^{poly{1/delta}}} time.

Shouldn't it be:

s^{n^{poly(delta)}} time?

oops, I meant:

ReplyDelete2^{n^{poly(delta)}} time.

Right. Fixed.

ReplyDeleteEven 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.

ReplyDeleteSomeone 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.

ReplyDeleteLots of people working on something does not make that thing "interesting".

ReplyDeleteThe 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

ReplyDelete> 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.

ReplyDeleteLots 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.

ReplyDeletePlease 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.