Thursday, December 01, 2005

The Unique Games Conjecture

At the recent FOCS conference, Subhash Khot gave a tutorial on the Unique Games Conjecture. You can see the slides of his talk here.

5 Comments:

Anonymous Anonymous said...

I was looking at Khot's original UGC paper, and had a couple of questions:

1) Is the Long code test an instance of a 2-Linear Equation mod 2 ? If not, how would Khot derive hardness of 2-lin mod 2 based on the verifier test proposed ?

2) In choosing a random function "f" to apply the longcode test it seems to me that we require O(n) random bits since there are 2^O(n) functions altogether.. where am I going wrong since the verifier is only allowed O(log n) bits after all ? This question would apply to Hastad's original 3-query test as well..

Thanks,
Anand.

7:15 PM  
Anonymous Anonymous said...

Ignore question (2) above. I see that the number of random bits is O(|\sigma|) (size of alphabet) not O(n).. In Khot's proof, |\sigma| = k is a function of \zeta and \delta, but it's still "constant" and n can be made much larger..

7:35 PM  
Blogger Ryan O'Donnell said...

Hi Anand --

The paper can be a little confusing because it is written in the "old-school" notation where instead of calling encodings f : {-1,1}^m -> {-1,1} and strings x, they call encodings A and strings f.

To answer question 1), yes this is a 2-LIN(2) test. If you look carefully near the top of page 5, you see that Subhash insists that the functions be "folded" (f(x) = -f(-x)). Thus when he tests

A(f) = A(f mu) -- in our notation, f(x) = f(x mu) -- this really might be a test like f(x) XOR b = f(x mu) XOR b', where b and b' are bits that facilitate folding. Thus this is really a 2-variable linear equation. Same deal for the A(f) = B(f o pi) test.

In fact, we have basically proven a strong result then this in class; the reason is:
a) Max-Cut constraints can be viewed as 2-LIN(2) constraints (x \neq y is equivalent to x + y = 1)
b) if you take rho = -1+2eps where eps is small, our tradeoff (1/2 - 1/2 rho vs. arccos(rho)/pi) is 1-eps vs. arccos(-1+2eps)/pi. And by Taylor expansion, arccos(-1+2eps)/pi is equal to 1 - Theta(sqrt(eps)).

1:25 PM  
Anonymous Anonymous said...

Thanks Ryan. I did notice that in the last class we spoke about 2-query tests.. interesting that both MAX-CUT and UGC should tend towards 2-LIN equations (or 2-query PCPs).

4:16 PM  
Anonymous Anonymous said...

Can you give more details as to where exactly do we use the uniqueness (of the unique grame conjecture) property in the proof of the hardness for max-cut. In other words, where would the proof fail if we were using the standard label cover reduction

8:18 AM  

Post a Comment

<< Home