The Abelian embedding conjecture for approximability of satisfiable kk-CSPs

About 2 years old · traced to

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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.