Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-273 | 11th October 2026 23:26

Universal Abelian Embedding and Affine Relaxation for CSP

RSS-Feed




TR26-273
Authors: Siu On Chan, Hiu Tsun Ng
Publication: 25th October 2026 07:48
Downloads: 8
Keywords: 


Abstract:

Bhangale, Khot, and Minzer (TheoretiCS 2026) proposed a hybrid approximation algorithm for certain satisfiable CSPs to exploit their abelian embeddings. We propose BasicSDP $\wedge$ CSinglAIP to simplify and generalize their hybrid algorithm. We do so by introducing two concepts:
(1) universal embedding, which simplifies and generalizes their master embedding, and
(2) affine relaxation in an abelian group.

We prove that our algorithm is not simulated by SDP+AIP, providing the first linear-level SDP+AIP lower bound for a tractable CSP. We also prove the first lower bounds for their hybrid algorithm, by turning our algorithm into a hierarchy and proving linear-level lower bounds, while achieving the optimal gap for large-arity CSPs.

A deeper understanding of our algorithms' power may lead to progress on uniform CSP algorithms and the optimal approximability of satisfiable CSPs.



ISSN 1433-8092 | Imprint