יום ראשון, 1.3.2009, 11:30
The direct product code encodes the truth table of a function f:U-->R by
a function f^k:U^k -->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.
Joint work with Valentine Kabanets and Russell Impagliazzo.