The Abelian embedding conjecture for approximability of satisfiable kk-CSPs

From papers

Let mumu be a distribution on Σk\Sigma^k. An Abelian embedding of mumu is an Abelian group GG and mappings σi:ΣG\sigma_i: \Sigma \rightarrow G, 1leqslantileqslantk1 leqslant i leqslant k, not all constant, such that

i=1kσi(ai)=0G\sum_{i=1}^k \sigma_i(a_i)=0_G

for every (a1,,ak)insupp(μ)(a_1,\ldots,a_k)in \mathsf{supp}(\mu). Here, Conclusion

is the paper's stated exponential-product high-degree conclusion for the distribution. **Abelian embedding conjecture.** For a distribution $\mu$ on $\Sigma^k$, Conclusion

holds if and only if μ\mu admits no Abelian embedding.

The claim proposes that the absence of Abelian embeddings is not only necessary, as shown by the character construction preceding the conjecture, but also sufficient for the relevant approximability conclusion. Its resolution is not specified in the supplied text.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Amey Bhangale, Subhash Khot, Yang P. Liu and Dor Minzer, “On Approximability of Satisfiable k-CSPs: VII”, arXiv:2411.15136 (2024).

Solutions 0

No solutions have been posted yet.