TR97-003 Authors: Sanjeev Arora, Madhu Sudan

Publication: 29th January 1997 13:40

Downloads: 2124

Keywords:

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) 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.