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 ≥ 2. 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 ≥ 4, it is known that an approximation ratio of [EQUATION], obtained by choosing a random assignment, is optimal, assuming P ≠ NP. For every k ≥ 2, an approximation ratio of at least 7/8 can be obtained for MAX NAE-{k}-SAT. There was some hope, therefore, that there is also a 7/8-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously.