TR09-090 Authors: Russell Impagliazzo, Valentine Kabanets, Avi Wigderson

Publication: 6th October 2009 19:36

Downloads: 1463

Keywords:

The “direct product code” of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)).

This basic construct underlies “hardness amplification” in cryptography, circuit complexity and

PCPs. Goldreich and Safra [GS00] pioneered its local testing and its PCP application. A recent

result by Dinur and Goldenberg [DG08] enabled for the first time testing proximity to this

important code in the “list-decoding” regime. In particular, they give a 2-query test which

works for polynomially small success probability 1/k, and show that no such test works below

success probability 1/k.

Our main result is a 3-query test which works for exponentially small success probability

exp(?k). Our techniques (based on recent simplified decoding algorithms for the same code

[IJKW08]) also allow us to considerably simplify the analysis of the 2-query test of [DG08]. We

then show how to derandomize their test, achieving a code of polynomial rate, independent of

k, and success probability 1/k.

Finally we show the applicability of the new tests to PCPs. Starting with a 2-query PCP

over an alphabet $\Sigma$ and with soundness error $1 ? \delta$, Rao [Rao08] (building on Raz’s (k-fold)

parallel repetition theorem [Raz98] and Holenstein’s proof [Hol07]) obtains a new 2-query PCP

over the alphabet $\Sigma^k$ with soundness error $exp(?\delta^2 k)$. Our techniques yield a 2-query PCP

with soundness error $exp(?\delta \sqrt{k})$. Our PCP construction turns out to be essentially the same as

the miss-match proof system defined and analyzed by Feige and Kilian [FK00], but with simpler

analysis and exponentially better soundness error.