Improved low-degree testing and its applications
Sanjeev Arora, Madhu Sudan · 1997
NP = PCP(log n, 1) and related results crucially depend upon the close connection betsveen 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 [29].The strongest previously known connection for this test states that a function passes the test with probability 6 for some d > 7/8 iff the function has agreement N 6 with a polynomial of degree d.We present a new, and surprisingly strong, analysis which shows thatthe preceding statementis true for 6<<0.5.The analysis uses a version of Hilbe?l irreducibility, a tool used in the factoring of multivariate polynomials.As a consequence we obtain an alternate construction for the following proof system: A constant prover l-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-10g* -''.Such a proof system, which implies the NP-hardness of approximating Set Cover to within fl(log n) factors, has already been obtained by Raz and Safra [28].Our result was completed after we heard of their claim.A second consequence of our analysis is a self testerlcorrector for any buggy program that (supposedly) computes a polynomial over a finite field.If the program is correct only on 6 fraction of inputs where 15<<0.5, then the tester/corrector determines J and generates 0(~) randomized programs, such that one of the programs is correct on every input, with high probability.