NP = PCP(log n, 1) and related results crucially depend upon the close connection between the probability with which a function passes a ``low degree test'' and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan. The strongest previously known connection for this test states that a function passes the test with probability delta for some delta >7/8 iff the function has agreement approximately delta with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for delta much smaller than 1/2. The analysis uses a version of {em Hilbert irreducibility}, a tool of algebraic geometry. As a consequence we obtain an alternate construction for the following proof system: A constant prover 1-round proof system for NP languages in which the verifier uses O(log n) random bits, receives answers of size O(log n) bits, and has an error probability of at most 2?log1?n . Such a proof system, which implies the NP-hardness of approximating Set Cover to within Omega(log n) factors, has already been obtained by Raz and Safra. Our result was completed after we heard of their claim. A second consequence of our analysis is a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field. If the program is correct only on delta fraction of inputs where delta is much smaller than 1/2, then the tester/corrector determines delta and generates O(1/delta) values for every input, such that one of them is the correct output. In fact, our techniques yield something stronger: Given the buggy program, we can construct O(1/delta) randomized programs such that one of them is correct on every input, with high probability.
展开▼
