Direct-Product Decoding and Testing, and 2-query PCPs
Valentine Kabanets, IAS and SFU
Theory Seminar, February 16, 2010

In this talk, I'll give an overview of two recent results on the problems of decoding and testing of the direct-product code (given a function f: U -> R, its k-wise DP encoding is f^k: U^k -> R^k, the k-tuples of values of f over all possible k-tuple of inputs).

In the joint work with Russell Impagliazzo, Ragesh Jaiswal, and Avi Wigderson, we gave an information-theoretically optimal (up to constant factors) efficient list-decoding algorithm for the DP code, as well as for Yao's XOR Lemma-based code. Using some of these ideas, in the later work with Russell and Avi, we also got a 3-query test for the DP code which can handle the exponentially-small acceptance probability (this corresponds to the "list-decoding regime" for testing), and a simple analysis of the 2-query test of [Dinur, Goldenberg]. Moreover, our decoding and testing results also apply to the case of derandomized DP code, where instead of all possible k-tuples of inputs to f, one considers a "pseudorandom" subset of k-tuples.

The original motivation to study the problem of DP testing [Goldreich, Safra] was an application to PCPs. Indeed, we're able to apply our new DP testing results to the problem of soundness amplification of 2-query PCPs, getting a version of "parallel repetition" for special kinds of 2-player games, similar to "miss-match" games of [Feige, Kilian].

This talk is based on the joint work with Russell Impagliazzo, Ragesh Jaiswal, and Avi Wigderson.