The Abelian embedding conjecture for approximability of satisfiable -CSPs
The Abelian embedding conjecture for approximability of satisfiable -CSPs
Let be a distribution on . An Abelian embedding of is an Abelian group and mappings , , not all constant, such that
for every . 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$, Conclusionholds if and only if 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
Sign in to submit a solution.
No solutions have been posted yet.