News for hackers. Stuff that matters.
Re:Subhash Khot and the Unique Games Conjecture by simplekoala on Tuesday August 12, 2014 @04:49PM (#8170069)
Feel humbled to read about him. Floored!
Re:Subhash Khot and the Unique Games Conjecture by krebby on Tuesday August 12, 2014 @10:45PM (#8171232)
Khot was one of my favorite professors at NYU and always lead on with way better and more in depth stories than the material presented initially. So great to read about his other successes.
Re:Subhash Khot and the Unique Games Conjecture by lotharbot on Tuesday August 12, 2014 @04:51PM (#8170081)
Re:Subhash Khot and the Unique Games Conjecture by scythe on Tuesday August 12, 2014 @05:26PM (#8170295)
I'm sort of curious about the scope of UGC. There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard, so how much harder does a problem have to be to invoke UGC? Is there a no-go result that prevents "translating" TSP approximations to the approximation of other problems?
Re:Subhash Khot and the Unique Games Conjecture by codeflo on Tuesday August 12, 2014 @07:12PM (#8170693)
> There are well-known approximation algorithms for the Traveling Salesman Problem, which is NP-hard

Actually, it's either not NP-hard, or not approximable, depending on your definition of TSP. Let me clarify.

TSP, as most people define it, means "given a graph, find the shortest roundtrip". As you rightly state, this problem can be well approximated. But it's not a decision problem (it doesn't have a yes/no answer), and thus doesn't even fit into categories like "NP" or "NP-complete". Talking about the NP-completess of this "Optimization TSP" is essentially a type error.

It's only when we define a "Decision TSP" problem that we can talk about things like NP-hardness. For example, we might ask "Given a graph and a number c, is there a roundtrip of length less than c?". And this new problem is NP-hard. Given any problem in NP, like a SAT instance for example, we can efficiently construct a (usually very contrived) graph that will have a roundtrip of a certain length if and only the original SAT instance is satisfiable.

But unlike "Optimization TSP", this "Decision TSP" can't be approximated. It doesn't even make sense to talk about approximations: a roundtrip of length < c can't "almost exist", the answer is always either yes or no. And while an exact solution for Optimization TSP can trivially answer Decision TSP, any approximation of Optimization TSP is essentially useless in solving Decision TSP.

That's why TSP (in its optimization form) can be easy to approximate, while also (in its decision form) being NP-hard.

Re:Subhash Khot and the Unique Games Conjecture by beagle3 on Wednesday August 13, 2014 @04:31AM (#8171962)
Great description. Obviously codeflo knows this, but it's worth pointing out that "roundtrip" means "visiting every city exactly once". Euclidean problem geometry guarantees it (it's always faster to go directly) but many problems, even though emerging from seemingly euclidean space, do not have this property - e.g. if you're using a car, the road network might induce non-euclidean distance geometry that would make the fast roundtrip include more than one visit to a node.
Re:Subhash Khot and the Unique Games Conjecture by anuragbiyani on Wednesday August 13, 2014 @01:40AM (#8171594)
Actually general version of TSP (optimization problem) cannot be approximated to a constant factor in polynomial time unless P = NP. [1]

Your confusion likely stem from the fact that metric-TSP (a special case of TSP problem where the distance between cities form a metric [2]) is actually APX-complete, which means it can be approximated to a constant factor in polynomial time (Christofides algorithm, approx ratio = 1.5).

PS: A potentially interesting aside - Sanjeev Arora, the PhD advisor of Subhash Khot actually got his first Gödel prize (2001) for discovering a PTAS (polynomial time approximation scheme, which in layman term means you can approximate it as close to real answer (but not exactly) as you like in polynomial time) for Euclidean-TSP (independently discovered by Joseph S. B. Mitchell as well). The algorithm make pretty interesting use of Dynamic programming, and was a surprise for the theoretical CS community that time.

[1] Brief intuition - HAMILTON-PATH (decision version) can be solved exactly in polynomial time using a constant factor poly time approximation of general TSP (optimization). But since, HAMILTON-PATH is proven to be NP-Complete, then P must equal NP (in which case we can solve all problems in NP and their optimization counterparts exactly in polynomial time anyway). For a formal proof see Khot's lecture notes: http://www.cs.nyu.edu/~khot/lec1.ps (you can find a variety of other similar resources as well, as this is one of the first impossibility proof in almost any graduate level approximation algorithm class).

[2] http://en.wikipedia.org/wiki/Metric_(mathematics)

Re:Subhash Khot and the Unique Games Conjecture by pavpanchekha on Tuesday August 12, 2014 @06:21PM (#8170522)
Yes. TSP is NP-complete, which means that exact solutions to TSP can be turned into exact solutions to any other NP problem in P time. However, there is no guarantee on how this transformation behaves on non-exact solutions. In fact, there are many problems that are known to be non-approximable. For example, Vertex Cover is known not to have approximation algorithms better than a factor of 1.3 or so (assuming P != NP). Maximum clique is completely inapproximable (it is impossible to approximate it to any constant factor).
Re:Subhash Khot and the Unique Games Conjecture by sssilver on Tuesday August 12, 2014 @11:01PM (#8171271)
Comic Sans killed it