The Taub Faculty of Computer Science Events and Talks

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.