The Taub Faculty of Computer Science Events and Talks

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.