New direct-product testers and 2-query PCPs

Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson

Abstract

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 pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg 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 by Impagliazzo et al.) also allow us to considerably simplify the analysis of the 2-query test of Dinur&Goldberg. 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 Σ and with soundness error 1-δ, Rao (building on Raz's (k-fold) parallel repetition theorem and Holenstein's proof) obtains a new 2-query PCP over the alphabet Σk with soundness error exp(-δ2 k). Our techniques yield a 2-query PCP with soundness error exp(-δ√k).

Our PCP construction turns out to be essentially the same as the miss-match proof system of Feige and Kilian, but with simpler analysis and exponentially better soundness error.

Versions