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.