## 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

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 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).