Name
Abstract | ||
|---|---|---|
Given a function f : X -{0,1}, its `ell’ wise direct productis the function F = f`ell : X^ell - {0,1}^ell defined by:F(x_1,...,x_ell)= (f(x_1),..,f(x_ell)).: We are interestedin the local testability of the direct product encoding(mapping f- f^ell). Namely, given an arbitrary functionF : X^ell-{0,1}^ell, we wish to determine how close itis to f`ell for some f : X-{0,1}, by making two randomqueries into F. In this work we analyze the case of lowacceptance probability of the test. We show that even ifthe test passes with small probability, epsilon 0, already Fmust have a non-trivial structure and in particular mustagree with some f^ell on nearly epsilon of the domain. Moreover,we give a structural characterization of all functions Fon which the test passes with probability epsilon.Our results can be viewed as a combinatorial analogof the low error ‘low degree test’, that is used in PCPconstructions. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1109/FOCS.2008.26 | FOCS |
Keywords | Field | DocType |
wise direct productis,arbitrary functionf,function f,probability epsilon,low error,low error range,lowacceptance probability,ifthe test,low degree test,testing direct product,small probability,direct product encoding,property testing,list decoding,random variables,probability,direct product,silicon,games,construction industry,testing,decoding,encoding | Testability,Discrete mathematics,Combinatorics,Random variable,Property testing,Direct product,Decoding methods,Sigma,List decoding,Mathematics,Encoding (memory) | Conference |
ISSN | Citations | PageRank |
0272-5428 | 15 | 0.75 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Elazar Goldenberg | 2 | 17 | 1.45 |