Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: New Direct Product Code Testers, and PCPs
event speaker icon
Avi Wigderson (IAS)
event date icon
Sunday, 01.03.2009, 11:30
event location icon
TBA
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.