Lune

SODA2021Top-tier venue

On the Mysteries of MAX NAE-SAT

Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick

Abstract

Abstract. 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 [Formula: see text] for some [Formula: see text]. We refer to this problem as MAX NAE-[Formula: see text]-SAT. For [Formula: see text], it is a slight extension of the celebrated MAX CUT problem. For [Formula: see text], it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For [Formula: see text], it is known that an approximation ratio of [Formula: see text], obtained by choosing a random assignment, is optimal, assuming [Formula: see text]. For every [Formula: see text], an approximation ratio of at least [Formula: see text] can be obtained for MAX NAE-[Formula: see text]-SAT. There was some hope, therefore, that there is also a [Formula: see text]-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no [Formula: see text]-approximation algorithm for MAX NAE-SAT, assuming the Unique Games Conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-[Formula: see text]-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 [Formula: see text]. Using calculus of variations, we extend the analysis of O’Donnell and Wu for MAX CUT to MAX NAE-[Formula: see text]-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-[Formula: see text]-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is about 0.9089. This gives a full understanding of MAX NAE-[Formula: see text]-SAT for every [Formula: see text]. Interestingly, the rounding function used by this optimal algorithm is the solution of an integral equation. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-[Formula: see text]-SAT with a conjectured approximation ratio of 0.8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0.8698. We further conjecture that these are essentially the best approximation ratios that can be achieved for these problems, assuming the UGC. Somewhat surprisingly, the rounding functions used by these approximation algorithms are nonmonotone step functions that assume only the values [Formula: see text].

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

5 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • MAX BISECTION might be harder to approximate than MAX CUT cites On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
  • MAX BISECTION might be harder to approximate than MAX CUT cites Tight approximability of MAX 2-SAT and relatives, under UGC
  • MAX BISECTION might be harder to approximate than MAX CUT cites On Approximability of Satisfiable k-CSPs: V
  • MAX BISECTION might be harder to approximate than MAX CUT cites Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers5

  1. SDPs and Robust Satisfiability of Promise CSPJoshua Brakensiek, Venkatesan Guruswami, Sai SandeepSTOC 2023 · 8 citations
  2. Separating MAX 2-AND, MAX DI-CUT and MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickFOCS 2023 · 3 citations
  3. On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPsSuprovat Ghoshal, Euiwoong LeeFOCS 2023 · 1 citation
  4. MAX BISECTION might be harder to approximate than MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickSODA 2026
  5. On Approximability of Satisfiable k-CSPs: VAmey Bhangale, Subhash Khot, Dor MinzerSTOC 2025

Builds on2

  1. Tight approximability of MAX 2-SAT and relatives, under UGCJoshua Brakensiek, Neng Huang, Uri ZwickSODA 2024 · 3 citations
  2. Separating MAX 2-AND, MAX DI-CUT and MAX CUTJoshua Brakensiek, Neng Huang, Aaron Potechin, Uri ZwickFOCS 2023 · 3 citations

Related papers

  1. Approximation Algorithms and Hardness for Strong Unique GamesSuprovat Ghoshal, Anand LouisSODA 2021 · 3 citations
  2. Are Graph Neural Networks Optimal Approximation Algorithms?Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu et al.NeurIPS 2024 · 23 citations
  3. Parameterized Approximation Scheme for Biclique-free Max k-Weight SAT and Max CoveragePallavi Jain, Lawqueen Kanesh, Fahad Panolan, Souvik Saha et al.SODA 2023 · 6 citations
  4. Subexponential LPs Approximate Max-CutSamuel B. Hopkins, Tselil Schramm, Luca TrevisanFOCS 2020 · 9 citations
  5. Constraint Satisfaction Problems with AdviceSuprovat Ghoshal, Konstantin Makarychev, Yury MakarychevSODA 2025
Dusk over the sea between two cliffs drawn in fine vertical lines