期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1997
卷号：1997
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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−log1−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.
关键词：approximability , constant prover proof systems , Low degree testing , multivariate polynomials , probabilistically checkable proofs , set cover
