Locally Testing Direct Product in the Low Error Range

by Irit Dinur and Elazar Goldenberg

New Direct Product Code Testers, and PCPs

by Valentine Kabanets, Russell Impagliazzo, and Avi Wigderson

Oded's comments

The object being investigated is the "direct product code" just as in the work Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized. However, there the task was (locally) decoding (at the list decoding regime), whereas here the task is (locally) testing (also at the list decoding regime). Locally testing this code (and its derandomization) was first considered by Muli Safra and myself in the mid 1990s, but while our original motivation was the list decoding regime, we were only able to deal with the unique decoding regime.
Testing in the list decoding regime means a characterization of the type of functions $F:U^k \to R^k$ that are accepted by the test with small (but not too small) probability. For the natural test that checks consistency on two random $k$-sequences of significant intersection (i.e., intersection size $m=sqrt(k)$ or so), such a characterization was provided in [1] for the case that the acceptance probability is $k^{-Omega(1)}$. It was also shown in [1] that this test cannot provide meaningful information for lower acceptance probability, in [2] showed that an alternative 3-query test can also handle exponentially small (in $k$) acceptance probability. Loosely spaeking, in both cases the characterization says that such passing $F$ fits a small (i.e., polynomially related to the acceptance probability) collection of functions $f:U \to R$ in the sense that for almost all $x=(x_1,...,x_k)\in D^k$ the value of $F(x)$ is close to the value $f(x_1),...,f(x_k)$.
The proofs proceed in two steps. The first step refers to a notion of "local" consistency, which means that we consider all $k$-sequences that contain a typical $m$-subset (and $k-m$ other arbitrary elements) and show that this set of $k$-subset fits a small collection of functions $f$. The second step shows that these different local views are actually "globally" consistent (i.e., they typically refer to the same collection of functions $f$). The intuition underlying both steps is that consistency of $F$ on two random $k$-sequences of intersection size $m$ implies similar consitency when the intersection size is $m+1$ or $2m$. (Be warned that the actual proofs are quite involved.)

The original abstract

The direct product code encodes the truth table of a function $f:U\to R$ by a function $f^k:U^k \to R^k$, which lists the value of $f$ in all $k$-tuples of inputs. We study its (approximate) proximity testing to this code in the ``list decoding" regime.
We give a 3-query tester for distance $1-exp(-k)$ (which is impossible with 2 queries). We also give a 2-query tester for distance $1-1/poly(k)$ for a derandomized version of this code (of polynomial rate).
We then use the same techniques to reduce soundness error in 2-query PCPs, which gives incomparable decay to the Parallel Repetition Theorem.

Back to list of Oded's choices.