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