On approximability of satisfiable k -CSPs: I

DOI10.1145/3519935.3520028MaRDI QIDQ6083552zbMATH OpenWikidataFDO

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)

Full work available at URL https://doi.org/10.1145/3519935.3520028

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

(6)

• Complexity theory. Abstracts from the workshop held June 2--7, 2024
• On approximability of satisfiable k-CSPs: II
• Approximate graph coloring and the crystal with a hollow shadow
• Algebraic approach to approximation
• Parallel repetition for the \textsf{GHZ} game: exponential decay
• Optimal inapproximability of promise equations over finite groups

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)