TY - JOUR

T1 - Improved low-degree testing and its applications

AU - Arora, Sanjeev

AU - Sudan, Madhu

N1 - Funding Information:
* Supported by an NSF CAREER award, an Alfred P. Sloan Fellowsh ip, and a Packard Fellowsh ip. † Part of th is work was done wh en th is auth or was at th e IBM Th omas J. Watson Research Center.

PY - 2003

Y1 - 2003

N2 - 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 δ for some δ> 7/8 iff the function has agreement ≈ δ with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small δ, provided the field size is polynomially larger than d/δ. The analysis uses a version of 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εn. Such a proof system, which implies the NP-hardness of approximating Set Cover to within Ω(log n) factors, has already been obtained by Raz and Safra, Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present. 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 δ fraction of inputs where δ = 1/Fε ≪ 0.5, then the tester/corrector determines δ and generates O(1/δ) values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct O(1/δ) randomized programs such that one of them is correct on every input, with high probability. Such a strong self-corrector is a useful tool in complexity theory - with some applications known.

AB - 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 δ for some δ> 7/8 iff the function has agreement ≈ δ with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small δ, provided the field size is polynomially larger than d/δ. The analysis uses a version of 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εn. Such a proof system, which implies the NP-hardness of approximating Set Cover to within Ω(log n) factors, has already been obtained by Raz and Safra, Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present. 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 δ fraction of inputs where δ = 1/Fε ≪ 0.5, then the tester/corrector determines δ and generates O(1/δ) values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct O(1/δ) randomized programs such that one of them is correct on every input, with high probability. Such a strong self-corrector is a useful tool in complexity theory - with some applications known.

UR - http://www.scopus.com/inward/record.url?scp=0347589496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0347589496&partnerID=8YFLogxK

U2 - 10.1007/s00493-003-0025-0

DO - 10.1007/s00493-003-0025-0

M3 - Article

AN - SCOPUS:0347589496

VL - 23

SP - 365

EP - 426

JO - Combinatorica

JF - Combinatorica

SN - 0209-9683

IS - 3

ER -