The new test enables us to prove a low-error characterization of NP in terms of PCP. Specifically, our theorem states that, for any given $\epsilon > 0$, membership in any NP language can be verified with $O(1)$ accesses, each reading logarithmic number of bits, and such that the error-probability is $2^{-\log^{1 -\epsilon}n}$. Our results are in fact stronger.
One application of the new characterization of NP is that approximating SET-COVER to within a logarithmic factors is NP-hard.
Previous analysis for low-degree--tests, as well as previous characterizations of NP in terms of PCP, have managed to achieve, with constant number of accesses, error-probability of, at best, a constant. The proof for the small error-probability of our new low-degree--test is, nevertheless, significantly simpler than previous proofs. In particular, it is combinatorial and geometrical in nature, rather than algebraic.
Joint work with S. Safra (Tel-Aviv University)