Revised: October 12, 2022
Published: October 2, 2023
Abstract: [Plain Text Version]
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).
Licensed under a Creative Commons Attribution License (CC-BY)