Balanced max 2-sat might not be the hardest

2007/06/11 by Per Austrin · 1 citation
Engineering · Computer Science · #graph theory and CDMA systems #Advanced Numerical Analysis Techniques #Coding theory and cryptography #Computer science

paper · doi:10.1145/1250790.1250818

openalex publication_date 2007/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX2SAT within αLLZ-+ε, where 0.9401 < αLLZ- < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick [28].

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Probabilistic checking of proofs
• Clique is hard to approximate within n1−ε
• A threshold of ln n for approximating set cover
• Proof verification and the hardness of approximation problems
• Maximizing Quadratic Programs: Extending Grothendieck's Inequality

Cited by

• 2-satisfiability [wikipedia]

Related

• Tight approximability of MAX 2-SAT and relatives, under UGC
• Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
• Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• On the Mysteries of MAX NAE-SAT