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),\dots,f(x_k))$. This basic construct underlies ``hardness amplification'' in cryptography, circuit complexity and PCPs. Goldreich and Safra \cite{GS00} pioneered its local \emph{testing} and its PCP application. A recent result by Dinur and Goldenberg~\cite{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 \emph{polynomially small} success probability $1/k^{\alpha}$, and show that no such test works below success probability $1/k$.

Our main result is a $3$-query test which works for \emph{exponentially small} success probability $\exp({-k^{\alpha}})$. Our techniques (based on recent simplified decoding algorithms for the same code \cite{IJKW08}) also allow us to considerably simplify the analysis of the 2-query test of \cite{DG08}. We then show how to \emph{derandomize} their test, achieving a code of polynomial rate, independent of $k$, and success probability $1/k^{\alpha}$.

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~\cite{Rao08} (building on Raz's ($k$-fold) parallel repetition theorem~\cite{Raz-parallel} and Holenstein's proof~\cite{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 of Feige and Kilian~\cite{FK00}, but with simpler analysis and exponentially better soundness error.

Versions