License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.11
URN: urn:nbn:de:0030-drops-99105
URL: http://drops.dagstuhl.de/opus/volltexte/2018/9910/
Go to the corresponding LIPIcs Volume Portal


Goldenberg, Elazar ; C. S., Karthik

Towards a General Direct Product Testing Theorem

pdf-format:
LIPIcs-FSTTCS-2018-11.pdf (0.6 MB)


Abstract

The Direct Product encoding of a string a in {0,1}^n on an underlying domain V subseteq ([n] choose k), is a function DP_V(a) which gets as input a set S in V and outputs a restricted to S. In the Direct Product Testing Problem, we are given a function F:V -> {0,1}^k, and our goal is to test whether F is close to a direct product encoding, i.e., whether there exists some a in {0,1}^n such that on most sets S, we have F(S)=DP_V(a)(S). A natural test is as follows: select a pair (S,S')in V according to some underlying distribution over V x V, query F 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 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=O_k(n). 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 k and n we provide a direct product domain V subseteq (n choose k) of size n, called the Sliding Window domain for which we prove direct product testability.

BibTeX - Entry

@InProceedings{goldenberg_et_al:LIPIcs:2018:9910,
  author =	{Elazar Goldenberg and Karthik C. S.},
  title =	{{Towards a General Direct Product Testing Theorem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9910},
  URN =		{urn:nbn:de:0030-drops-99105},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.11},
  annote =	{Keywords: Property Testing, Direct Product, PCP, Johnson graph, Ramanujan Complex, Derandomization}
}

Keywords: Property Testing, Direct Product, PCP, Johnson graph, Ramanujan Complex, Derandomization
Seminar: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 23.11.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI