The Direct Product encoding of a string @math on an underlying domain @math , is a function DP @math which gets as input a set @math and outputs @math restricted to @math . In the Direct Product Testing Problem, we are given a function @math , and our goal is to test whether @math is close to a direct product encoding, i.e., whether there exists some @math such that on most sets @math , we have @math DP @math . A natural test is as follows: select a pair @math according to some underlying distribution over @math , query @math on this pair, and check for consistency on their intersection. Note that the above distribution may be viewed as a weighted graph over the vertex set @math and is referred to as a test graph. The testability of direct products was studied over various specific domains and test graphs (for example see Dinur-Steurer [CCC'14]; Dinur-Kaufman [FOCS'17]). In this paper, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem? Towards this goal we introduce the notion of coordinate expansion of a test graph. Roughly speaking a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion then it admits a direct product testing theorem. Additionally, for every @math and @math we provide a direct product domain @math of size @math , called the Sliding Window domain for which we prove direct product testability.
@cite_0: 
@cite_3: The “direct-product code” of a function @math gives its values on all @math -tuples @math . This basic construct underlies “hardness amplification” in cryptography, circuit complexity, and probabilistically checkable proofs (PCPs). Goldreich and Safra [SIAM J. Comput., 29 (2000), pp. 1132--1154] pioneered its local testing and its PCP application. A recent result by Dinur and Goldenberg [Proceedings of the Forty-Ninth Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 613--622] enabled for the first time testing proximity to this important code in the “list-decoding” regime. In particular, they give a @math -query test which works for polynomially small success probability @math and show that no such test works below success probability @math . Our main result is a @math -query test which works for exponentially small success probability @math . Our techniques (based on recent simplified decoding algorithms for the same code [R. , Proceeding...
@cite_12: Given a function f : X rarr Sigma, its lscr-wise direct product is the function F = flscr : Xlscr rarr Sigmalscr defined 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 : Xlscr rarr Sigmalscr, we wish to determine how close it is to flscr for 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 flscr on 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.
We remark that the direct product testability question was further analyzed in the low acceptance regime under the domain @math , see @cite_12 @cite_3 @cite_0 and also under the domain where the universe is @math , and the domain is the set of all subspaces of @math @cite_3 .