Improved low-degree testing and its applications

        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^{-\log^{1 - \epsilon} 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) randomized programs such that one of them is correct on every input, with high probability.

By: Sanjeev Arora and Madhu Sudan

Published in: RC20746 in 1997


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.

Questions about this service can be mailed to .