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(x_{1}), ...,f(x_{k})). 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
- journal version in SIAM Journal on Computing, 41(6), pages 1722-1768, 2012 (special STOC'09 issue).
- extended abstract in Proceedings of the Forty-First ACM Symposium on Theory of Computing (STOC'09), pages 131-141, 2009.