On Approximability of Satisfiable k-CSPs: III

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 [BKM22b] 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] qn → 0, 1 qn where q ∈ (0, 1). We show that, for every constant ε > 0, if the test passes with probability ε > 0, then there is a global function g : [n] → 0, 1 such that for at least δ(ε) fraction of sets, the global function g agrees with the given table on all except α(ε) many locations. The novelty of this result lies in the fact that α(ε) is independent of the set sizes. Prior to our work, such a conclusion (in fact, a stronger conclusion with α = 0) was shown by Dinur, Filmus, and Harsha [DFH19] albeit when the test accepts with probability 1 -ε for a small constant ε > 0. The setting of parameters in our direct product tests is fundamentally different compared to [DG08, IKW12, DS14, DFH19] 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 [BKLM22].

As one application of our structural result, we give a 4-query linearity test under the p-biased distribution. More specifically, for any p ∈ ( 1 3 , 2 3 ), we give a test that queries a given function f : 0, 1 n → 0, 1 at 4 locations, where the marginal distribution of each query is µ ⊗n p . The test has perfect completeness and soundness 1 2 + ε -in other words, for every constant ε > 0, if the test passes with probability at least 1 2 + ε, then the function f is correlated to a linear function under the µ ⊗n p measure. This qualitatively improves the results on the linearity testing under the p-biased distribution from the previous work [KS09, DFH19] in which the authors studied the test with soundness 1 -ε, for ε close to 0.