[Colloquium] Talk by Valentine Kabanets, SFU and IAS on February 16, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, February 16, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Valentine Kabanets

From:		Simon Fraser University and Institute for Advanced Study

Web page:	http://www.cs.sfu.ca/~kabanets/

Title:	Direct-Product Decoding and Testing, and 2-query PCPs

Abstract: 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.


Please note that refreshments will be served prior to the talk at 2:30 in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100128/cc17f4de/attachment.htm