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 \{x_{i_1} \vee x_{i_2} \vee x_{i_3} | i1,i2,i3 \in [1,n], \x_{u}\in{\text{true},\text{false}}\} , 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 \frac{7}{8} , that is we can expect from this algorithm to have satisfied \frac{7}{8} 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 \frac{7}{8} + \epsilon 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, log(n) random bits) implies the previous fact.

The main topic of the tutorial was the Unique Games Conjecture, see the part 2. For a clear explaination of all the stuff: Computational Complexity: A Modern Approach


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: