On Approximability of Satisfiable k-CSPs: II

Let ς be an alphabet and μ be a distribution on ςk for some k ≥ 2. Let α > 0 be the minimum probability of a tuple in the support of μ (denoted supp(μ)). Here, the support of μ is the set of all tuples in ςk that have a positive probability mass under μ. We treat the parameters ς, k, μ, α as fixed and constant. We say that the distribution μ has a linear embedding if there exist an Abelian group G (with the identity element 0G) and mappings σi : ς → G, 1 ≤ i ≤ k, such that at least one of the mappings is non-constant and for every (a1, a2, ak) supp(μ), 'i=1k σi(ai) = 0G. Let fi: ςn→ [-1,1] be bounded functions, such that at least one of the functions fi essentially has degree at least d, meaning that the Fourier mass of fi on terms of degree less than d is negligible, say at most-. In particular, |E[fi]| ≤-. The Fourier representation is w.r.t. the marginal of μ on the ith co-ordinate, denoted (ς, μi). If μ has no linear embedding (over any Abelian group), then is it necessarily the case that |E(x1,.,x2,.,.,.,xk)1/4.,μ-.,n[f1(x1)f2(x2)¯.,fk(xk)].,.,=.,od,.,-(1),where the right hand side → 0 as the degree d → ∞ and δ→ 0? In this paper, we answer this analytical question fully and in the affirmative for k=3. We also show the following two applications of the result. The first application is related to hardness of approximation. We show that for every 3-ary predicate P:ς3 → {0,1} such that P has no linear embedding, an SDP integrality gap instance of a P-CSP instance with gap (1,s) can be translated into a dictatorship test with completeness 1 and soundness s+o(1), under certain additional conditions on the instance. The second application is related to additive combinatorics. We show that if the distribution μ on ς3 has no linear embedding, marginals of μ are uniform on ς, and (a,a,a) supp(μ) for every a ς, then every large enough subset of ςn contains a triple (x1, x2,x3) from μ-n (and in fact a significant density of such triples).