Prev: Divisor Products:
Next: Four (Double-Meaning) Lines May Have Solved a Problem
From: foo on 29 Mar 2010 05:12
Hi all,

I am reading Madhu Sudan's lecture notes about PCP theorem, consisting
of four lectures, available at http://people.csail.mit.edu/madhu/pcp/course.html

There is a place I just do not understand in the second lecture, about
the proof of PCP[O(logn), polylogn]=NP. The proof employs the low-
degree testing asking whether a polynomial is of low degree, i.e.,
degree bounded by d=polylogn. Then, In Theorem 2, P19, it is claimed
that if a polynomial is not of low degree, then it is rejected with
probability not greater than \delta only when it is 2\delta-close to a
low-degree polynomial.

But I cannot see why the testing rejects polynomials not of low degree
with high probability. After all, the probability is merely delta, and
according to the lecture notes we have \delta<O(1)/(d+1) where
d=polylogn. So we need to repeat the testing \Omega(1/\delta)=polylogn
times to raise the probability up to a constant. Right? But then the
random bits we used will not be bounded by O(logn).

That is what I do not understand. I will be grateful if someone can
help me. Thanks.
 | 
Pages: 1
Prev: Divisor Products:
Next: Four (Double-Meaning) Lines May Have Solved a Problem