Limits of Approximation Algorithms: PCPs and Unique Games (Part 1: PCPs)
August 8, 2009
Three weeks ago I have been to a workshop entitled “Limits of approximation algorithms: PCPs and unique games“, the travel expenses were kindly covered by DIMACS. Really nice university in New Jersey. But, guys, New Jersey is not for those without a car.
I will give a rough explaination of the complicated, intricated, probabilistical, fouriertical, technicals but still fascinating concepts around here.
So what is a PCP? It is a Probabilistically Checkable Proof, that is a mathematical proof whose correcteness can be checked by looking at it in random places. Indeed it is something more, it is locally testable, that is we need few bits. And indeed only a constant number of bits, 3.
It does not look so new until here, we can just take a mathematical proof and convert it with some error correcting code trick and get an object with higher redundance. The technique used here is the Fourier transform on the boolean cube, wonderful and versatile tool. (Don’t lose the majority is stablest theorem, really cool)
On the other side we have the mighty NP, the class of problems whose solutions can be checked in polynomial time. This class is really powerful. For example one problem that is in NP is the one of satysfying all the formulas in a set , each formula is an OR of three variables, those can be also negative, of course. This problem is called MAX-3SAT. A solution can be checked in polynomial time. Finding it may require trying all the possibilities around.
Now imagine that we are more modest and we simply want to maximize a lot of these clauses, a substantial percentage of the maximum number of them satisfiable for an istance of the problem. One very simple algorithm is going random: try a lot of random assignments! If you think for a while to this algorithm you may see that the approximation of this algorithm is , that is we can expect from this algorithm to have satisfied of the satisfiable clauses. Not so bad for a random typing monkey.
Ok, now it comes the hardness of approximation: we cannot get a polynomial time algorithm, for this problem, that does better than the random typing monkey! That is, if we have one that give us satisfied clauses then P would be equal to NP, and as a friend of mine says we would be like god, or we could just get 1’000’000 dollars.
Wonderful. Where is the PCP? Well a proof of Hastad that NP = PCP(3 queries, random bits) implies the previous fact.