Neng Huang

# On the Mysteries of MAX NAE-SAT

MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size $$k$$, for some $$k\geq2$$. We refer to this problem as MAX NAE-$${k}$$-SAT. For $$k=2$$, it is essentially the celebrated MAX CUT problem. For $$k=3$$, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For $$k\geq4$$, it is known that an approximation ratio of $$1-{1}/{2}^{k-1}$$, obtained by choosing a random assignment, is optimal, assuming P ≠ NP. For every $$k\geq2$$, an approximation ratio of at least 78 can be obtained for MAX NAE-$${k}$$-SAT. There was some hope, therefore, that there is also a 78-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously.

In this talk, we prove that there is no 78-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-{3,5}-SAT (i.e., MAX NAE-SAT where all clauses have size 3 or 5), the best approximation ratio that can be achieved, assuming UGC, is at most 0.8739.

Joint work with Joshua Brakensiek, Aaron Potechin and Uri Zwick.