Abstract
Given a function f:[N]^k>[M]^k, the Ztest is a three query test for checking if a function f is a direct product, namely if there are functions g_1,...g_k:[N]>[M] such that f(x_1,...,x_k)=(g_1(x_1),...,g_k(x_k)) for every input x in [N]^k.
This test was introduced by Impagliazzo et. al. (SICOMP 2012), who showed that if the test passes with probability epsilon > exp(sqrt k) then f is Omega(epsilon) close to a direct product function in some precise sense. It remained an open question whether the soundness of this test can be pushed all the way down to exp(k) (which would be optimal). This is our main result: we show that whenever f passes the Z test with probability epsilon > exp(k), there must be a global reason for this: namely, f must be close to a product function on some Omega(epsilon) fraction of its domain.
Towards proving our result we analyze the related (twoquery) Vtest, and prove a "restricted global structure" theorem for it. Such theorems were also proven in previous works on direct product testing in the small soundness regime. The most recent work, by Dinur and Steurer (CCC 2014), analyzed the V test in the exponentially small soundness regime. We strengthen their conclusion of that theorem by moving from an "in expectation" statement to a stronger "concentration of measure" type of statement, which we prove using hypercontractivity. This stronger statement allows us to proceed to analyze the Z test.
We analyze two variants of direct product tests. One for functions on ordered tuples, as above, and another for functions on sets of size k. The work of Impagliazzo et al. was actually focused only on functions of the latter type, i.e. on sets. We prove exponentially small soundness for the Ztest for both variants. Although the two appear very similar, the analysis for tuples is more tricky and requires some additional ideas.
BibTeX  Entry
@InProceedings{dinur_et_al:LIPIcs:2017:7533,
author = {Irit Dinur and Inbal Livni Navon},
title = {{Exponentially Small Soundness for the Direct Product ZTest}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {29:129:50},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770408},
ISSN = {18688969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7533},
URN = {urn:nbn:de:0030drops75336},
doi = {10.4230/LIPIcs.CCC.2017.29},
annote = {Keywords: Direct Product Testing, Property Testing, Agreement}
}
Keywords: 

Direct Product Testing, Property Testing, Agreement 
Seminar: 

32nd Computational Complexity Conference (CCC 2017) 
Issue Date: 

2017 
Date of publication: 

21.07.2017 