Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Toward a General Direct Product Testing Theorem

Toward a General Direct Product Testing Theorem 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. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Toward a General Direct Product Testing Theorem

Download PDF
18 pages

Loading next page...
 
/lp/association-for-computing-machinery/toward-a-general-direct-product-testing-theorem-nFRaori9mi
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3369939
Publisher site
See Article on Publisher Site

Abstract

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.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: Dec 16, 2019

Keywords: Direct product

References

  • Improved low-degree testing and its applications
    Arora, Sanjeev; Sudan, Madhu
  • Cube vs
    Bhangale, Amey; Dinur, Irit; Navon, Inbal Livni
  • The smallest eigenvalues of Hamming graphs, Johnson graphs and other distance-regular graphs with classical parameters
    Brouwer, Andries E.; Cioaba, Sebastian M.; Ihringer, Ferdinand; McGinnis, Matt
  • Direct sum testing
    David, Roee; Dinur, Irit; Goldenberg, Elazar; Kindler, Guy; Shinkar, Igor
  • Locally testing direct product in the low error range
    Dinur, Irit; Goldenberg, Elazar
  • List decoding with double samplers
    Dinur, Irit; Harsha, Prahladh; Kaufman, Tali; Navon, Inbal Livni; Ta-Shma, Amnon
  • High dimensional expanders imply agreement expanders
    Dinur, Irit; Kaufman, Tali
  • On non-optimally expanding sets in Grassmann graphs
    Dinur, Irit; Khot, Subhash; Kindler, Guy; Minzer, Dor; Safra, Muli
  • Exponentially small soundness for the direct product z-test
    Dinur, Irit; Navon, Inbal Livni
  • Assignment testers: Towards a combinatorial proof of the PCP theorem
    Dinur, Irit; Reingold, Omer
  • Direct product testing
    Dinur, Irit; Steurer, David
  • A combinatorial consistency lemma with application to proving the PCP theorem
    Goldreich, Oded; Safra, Shmuel
  • New direct-product testers and 2-query PCPs
    Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
  • Small set expansion in the Johnson graph
    Khot, Subhash; Minzer, Dor; Moshkovitz, Dana; Safra, Muli
  • A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP
    Raz, Ran; Safra, Shmuel