Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Aditya Anand, Euiwoong Lee, Davide Mazzali +1

This paper studies complete $k$-Constraint Satisfaction Problems (CSPs), where an $n$-variable instance has exactly one nontrivial constraint for each subset of $k$ variables, i.e.…