דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Local testing of direct products
event speaker icon
עירית דינור, מכון וייצמן למדע
event date icon
יום ראשון, 10.2.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
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.
[בחזרה לאינדקס האירועים]