Access the full text.
Sign up today, get DeepDyve free for 14 days.
The direct product encoding of a string a 0,1n on an underlying domain V (k[n]) is a function DPV(a) that gets as input a set S V and outputs a restricted to S. In the direct product testing problem, we are given a function F:V 0,1k, and our goal is to test whether F is close to a direct product encoding—that is, whether there exists some a 0,1n such that on most sets S, we have F(S)=DPV(a)(S). A natural test is as follows: select a pair (S,S) V according to some underlying distribution over V V, query F on this pair, and check for consistency on their intersection. Note that the preceding distribution may be viewed as a weighted graph over the vertex set V and is referred to as a test graph. The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC’14) analyzed it when V equals the k-th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS’17) analyzed it for the case where V is the set of faces of a Ramanujan complex, where in this case V=Ok(n). In this article, 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, it admits a direct product testing theorem. Additionally, for every k and n, we provide a direct product domain V (kn) of size n, called the sliding window domain, for which we prove direct product testability.
ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery
Published: Dec 16, 2019
Keywords: Direct product
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.