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.