New Direct-Product Testers and 2-Query PCPs

The “direct-product code” of a function f gives its values on all k-tuples (f(x₁),, f(xₖ)). This basic construct underlies “hardness amplification” in cryptography, circuit complexity, and probabilistically checkable proofs (PCPs). Goldreich and Safra [SIAM J. Comput., 29 (2000), pp. 1132--1154] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 613--622] 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 [R. Impagliazzo et al., Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 579--588]) also allow us to considerably simplify the analysis of the 2-query test of [Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 613--622]. 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 with a projection property over an alphabet Σ and with soundness error 1-δ, Rao [Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, 2008, pp. 1--10] (building on Raz's (k-fold) parallel repetition theorem [R. Raz, SIAM J. Comput., 27 (1998), pp. 763--803] and Holenstein's proof [T. Holenstein, Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, 2007, pp. 411--419] obtains a new 2-query PCP over the alphabet Σᵏ with soundness error exp(-δ² 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 defined and analyzed by Feige and Kilian [SIAM J. Comput., 30 (2000), pp. 324--346] but with simpler analysis and exponentially better soundness error.