Locally Testing Direct Product in the Low Error Range
Irit Dinur, Elazar Goldenberg · 2008
Given a function f : X rarr Sigma, its lscr-wise direct product is the function F = flscr: Xlscrrarr Sigmalscrdefined by: F(x1,...,xlscr) = (f(x1),...,f(xlscr)). We are interested in the local testability of the direct product encoding (mapping f rarr flscr). Namely, given an arbitrary function F : Xlscrrarr Sigmalscr, we wish to determine how close it is to flscrfor some f : X rarr Sigma, by making two random queries into F. In this work we analyze the case of low acceptance probability of the test. We show that even if the test passes with small probability, epsiv>0, already F must have a non-trivial structure and in particular must agree with some flscron nearly epsiv of the domain. Moreover, we give a structural characterization of all functions F on which the test passes with probability epsiv. Our results can be viewed as a combinatorial analog of the low error dasialow degree testpsila, that is used in PCP constructions.