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..
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..
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)).
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).
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
5 Comments:
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.
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..
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)).
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).
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
Post a Comment
<< Home