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

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Local testing of direct products
event speaker icon
Irit Dinur (Weizmann Institute of Science)
event date icon
Sunday, 10.02.2008, 11:00
event location icon
Room 337-8 Taub Bld.
Given a function f:[n]-->{0,1}, its k-wise direct product encoding is the function F:[n]^k --> {0,1}^k defined by F(x_1,..x_k) = (f(x_1),...,f(x_k)) This simple "encoding" is useful in PCP-like settings, when we want to simulate reading k arbitrary values of f by accessing only a constant number of inputs of the encoding F. The main challenge is to test that a given F is indeed a "correct" encoding of some f by reading only few (ultimately 2) random values in F. This is called a local consistency test. In particular, we will focus on the `natural' 2-query consistency test and analyze it in the small acceptance probability range, that corresponds to "list decoding".

Based on joint work with Elazar Goldenberg.