On approximability of satisfiable k -CSPs: I

DOI10.1145/3519935.3520028WikidataQ130976097 ScholiaQ130976097MaRDI QIDQ6083552FDOQ6083552

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)

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

zbMATH Keywords

constraint satisfaction problemshardness of approximationnon-abelian groups

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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)