On approximability of satisfiable k -CSPs: I

DOI10.1145/3519935.3520028MaRDI QIDQ6083552WikidataFDO

Authors Amey Bhangale, Subhash Khot, Dor Minzer

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

zbMATH Keywords

constraint satisfaction problemshardness of approximationnon-abelian groups

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Approximating satisfiable satisfiability problems (extended abstract)
• On the efficient approximability of constraint satisfaction problems
• The approximability of constraint satisfaction problems
• An approximation algorithm for \(\#k\)-SAT
• Approximating satisfiable satisfiability problems
• On the complexity of \(k\)-SAT
• On the Approximation of Maximum Satisfiability
• On the parameterized complexity of \((k,s)\)-SAT
• Approximation Algorithms for CSPs

Cited in

(1)

• Complexity theory. Abstracts from the workshop held June 2--7, 2024

This page was built for publication: On approximability of satisfiable k -CSPs: I

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083552)