Given a fixed arity k >= 2, Min-k-CSP on complete instances is the problem whose input consists of a set of n variables V and one (nontrivial) constraint for every k-subset of variables (so there are $binom{n}{k}$ constraints), and the goal is to find an assignment that minimizes the number of unsatisfied constraints. Unlike Max-k-CSP that admits a PTAS on more general dense or expanding instances, the approximability of Min-k-CSP has not been well understood. Moreover, for some CSPs including Min-k-SAT, there is an approximation-preserving reduction from general instances to dense and expanding instances, leaving complete instances as a unique family that may admit new algorithmic techniques.

In this paper, we initiate the systematic study of Min-CSPs on complete instances. First, we present an O(1)-approximation algorithm for Min-2-SAT on complete instances, the minimization version of Max-2-SAT. Since O(1)-approximation on dense or expanding instances refutes the Unique Games Conjecture, it shows a strict separation between complete and dense/expanding instances.

Then we study the decision versions of CSPs, whose goal is to find an assignment that satisfies all constraints; an algorithm for the decision version is necessary for any nontrivial approximation for the minimization objective. Our second main result is a quasi-polynomial time algorithm for every Boolean k-CSP on complete instances, including Min-k-SAT. We complement this result by giving additional algorithmic and hardness results for CSPs with a larger alphabet, yielding a characterization of (arity, alphabet size) pairs that admit a quasi-polynomial time algorithm on complete instances.

Euiwoong Lee is an assistant professor at the University of Michigan. He got his Ph.D. from Carnegie Mellon University in 2017 and worked as a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley and a postdoc at New York University. His research interests lie in several topics of theoretical computer science including approximation algorithms and hardness of approximation. His work has been recognized by several awards, including NSF CAREER Award, Edmund M. Clarke Dissertation Award, and ICALP Best Student Paper Award.