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 by supp(µ)). 1 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 0 G ) and mappings σ i : Σ → G, 1 i k, such that at least one of the mappings is non-constant and for every (a 1 , a 2 , . . . , a k ) ∈ supp(µ), k i=1 σ i (a i ) = 0 G . In [5], the authors asked the following analytical question.