Theory of Computing
-------------------
Title     : Exponentially Small Soundness for the Direct Product Z-test
Authors   : Irit Dinur and Inbal Livni Navon
Volume    : 19
Number    : 3
Pages     : 1-56
URL       : https://theoryofcomputing.org/articles/v019a003

Abstract
--------

Given a function $\f:[N]^k\rightarrow[M]^k$\,, the Z-test is a three-
query test for checking if the function $\f$ is a direct product,
i.e., if there are functions $\pf_1,\ldots,\pf_k:[N]\to[M]$ such that
$\f(x_1,\ldots,x_k)=(\pf_1(x_1),\ldots,\pf_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)$ correlated 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$ is
$\Omega(\epsilon)$ correlated to a direct product function, in the
same sense of closeness.

Towards proving our result we analyze the related (two-query) V-test,
and prove a "restricted global structure" theorem for it. Such
theorems were also proven in previous work on direct product testing
in the small soundness regime. The most recent paper, by Dinur and
Steurer (CCC 2014), analyzed the V test in the exponentially small
soundness regime. We strengthen their conclusion by moving from an "in
expectation" statement to a stronger "concentration of measure" type
of statement, which we prove using reverse hyper-contractivity. This
stronger statement allows us to proceed to analyze the Z test.


------------------

A preliminary version of this paper appeared in the
Proceedings of the 32nd Computational Complexity Conference (CCC'17).