Max-3-Lin over non-abelian groups with universal factor graphs

DOI10.1007/s00453-023-01115-1arXiv2111.09256OpenAlexW3211926474MaRDI QIDQ6053470

Aleksa Stanković, Amey Bhangale

Publication date: 27 September 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.09256

zbMATH Keywords

representation theoryconstraint satisfaction problemshardness of approximationnon-abelian groupslabel coveruniversal factor graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Inapproximability results for equations over finite groups
• Universal Factor Graphs
• Universal Factor Graphs for Every NP-Hard Boolean CSP.
• Proof verification and the hardness of approximation problems
• Approximation Resistance from Pairwise-Independent Subgroups
• Parallel Repetition in Projection Games and a Concentration Bound
• Relations between average case complexity and approximation complexity
• Probabilistic checking of proofs
• Interactive proofs and the hardness of approximating cliques
• A Parallel Repetition Theorem
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Sum of squares lower bounds for refuting any CSP
• Algebraic approach to promise constraint satisfaction
• $(2+\varepsilon)$-Sat Is NP-hard
• Some optimal inapproximability results
• The PCP theorem by gap amplification

This page was built for publication: Max-3-Lin over non-abelian groups with universal factor graphs