In this paper we study functions on the Boolean hypercube that have the property that after applying certain random restrictions, the restricted function is correlated to a linear function with non-negligible probability. If the given function is correlated with a linear function then this property clearly holds. Furthermore, the property also holds for low-degree functions as low-degree functions become a constant function under a random restriction with a non-negligible probability. We show that this essentially is the only possible reason. More specifically, we show that the function must be correlated to a product of a linear function and a low-degree function. One of the main motivations of studying this question comes from the recent work of the authors [Bhangale, Khot and Minzer, STOC 2021] towards understanding approximability of satisfiable Constraint Satisfaction Problems.
Towards proving our structural theorem, we analyze a $2$-query direct product test for the table $F: {[n]\choose qn} \rightarrow \{0,1\}^{qn}$ where $q\in (0,1)$. We show that, for every constant $\varepsilon>0$, if the test passes with probability $\varepsilon>0$, then there is a global function such that for at least $\delta(\varepsilon)$ fraction of sets, the global function agrees with the given table on {\em all except $\alpha(\varepsilon)$ many locations}. The novelty of this result lies in the fact that $\alpha(\varepsilon)$ is independent of the set sizes. Prior to our work, such a conclusion (in fact, a stronger conclusion with $\alpha = 0$) was shown in [Dinur-Filmus-Harsha, SODA 2019] albeit when the test accepts with probability $1-\varepsilon$ for a small constant $\varepsilon>0$. The setting of parameters in our direct product tests is fundamentally different compared to [Dinur-Goldenberg, FOCS 2008], [Impagliazzo-Kabanets-Wigderson, SIAM Journal of Computing 2012], [Dinur-Steurer, CCC 2014], [Dinur-Filmus-Harsha, SODA 2019] and hence our analysis involves new techniques, including the use of the small-set expansion property of graphs defined on multi-slices. Such expansion property was recently shown in [Braverman-Khot-Lifshitz-Minzer, FOCS 2022].
As one application of our structural result, we give a $4$-query linearity test under the $p$-biased distribution. More specifically, for any $p\in (\frac{1}{3},\frac{2}{3})$, we give a test that queries a given function $f: \{0,1\}^n \rightarrow \{0,1\}$ at $4$ locations, where the marginal distribution of each query is $\mu_p^{\otimes n}$. The test has perfect completeness and soundness $\frac{1}{2}+\varepsilon$ -- in other words, for every constant $\varepsilon>0$, if the test passes with probability at least $\frac{1}{2}+\varepsilon$, then the function $f$ is correlated to a linear function under the $\mu_p^{\otimes n}$ measure. This qualitatively improves the results on the linearity testing under the $p$-biased distribution from the previous work [Kopparty-Saraf, APPROX/RANDOM 2009] and [Dinur-Filmus-Harsha, SODA 2019] in which the authors studied the test with soundness $1-\varepsilon$.
