Theory Seminar: Local testing of direct products

Irit Dinur (Weizmann Institute of Science)

Sunday, 10.02.2008, 11:00

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.

Based on joint work with Elazar Goldenberg.