NP = PCP(logn, 1) andrelated results crucially depend upon the close connectionbetween the probability with which a function passes alow degree test and thedistance of this function to the nearest degreed polynomial. In this paperwe study a test proposed by Rubinfeld and Sudan [30]. Thestrongest previously known connection for this test states thata function passes the test with probability δ for some δ >7/8 iff the function has agreement ≈ δ with a polynomial ofdegreed. We present a new,and surprisingly strong, analysis which shows that the precedingstatement is true for arbitrarily small ≈, provided the fieldsize is polynomially larger than d/δ. The analysis uses aversion ofHilbertirreducibility, a tool of algebraic geometry.

As a consequence we obtain an alternate construction forthe following proof system: A constant prover 1-round proofsystem for NP languages in which the verifier usesO(logn) random bits, receives answers ofsizeO(logn) bits, and has an errorprobability of at most\( 2^{{ - \log ^{{1 - \in }} n}} \). Such a proof system,which implies the NP-hardness of approximating Set Cover towithin Ω(logn) factors, hasalready been obtained by Raz and Safra [29]. Raz and Safraobtain their result by giving a strong analysis, in the sensedescribed above, of a new low-degree test that theypresent.

A second consequence of our analysis is a selftester/corrector for any buggy program that (supposedly)computes a polynomial over a finite field. If the program iscorrect only on δ fraction of inputs where\( \delta = 1/{\left| F \right|}^{ \in } \ll 0.5 \), then thetester/corrector determines δ and generates\( O{\left( {\frac{1} {\delta }} \right)} \) values for every input,such that one of them is the correct output. In fact, ourresults yield something stronger: Given the buggy program, wecan construct\( O{\left( {\frac{1} {\delta }} \right)} \) randomized programs such that one of them iscorrect on every input, with high probability. Such a strongself-corrector is a useful tool in complexity theory—with someapplications known.

Authors and Affiliations

1. Department of Computer Science, Princeton University, 35 Olden St, Princeton, NJ, 08540, USA

   Sanjeev Arora*

2. Laboratory for Computer Science, MIT, Cambridge, MA, 02139, USA

   Madhu Sudan†

Corresponding author

Correspondence toSanjeev Arora*.

* Supported by an NSF CAREER award, an Alfred P.Sloan Fellowship, and a Packard Fellowship.

† Part of this work was done when this author was atthe IBM Thomas J. Watson Research Center.

Reprints and permissions