Overview:
In constraint satisfaction problems (CSPs), we are
given a set of constraints and we are asked to satisfy as many
of them as possible. A natural question about CSPs is as
follows. For a given type of CSP, what is the best approximation
ratio that we can guarantee between the number of constraints
satisfied by our solution (which we find with a probabilistic
polynomial time algorithm) and the maximum possible number of
constraints that can be satisfied?
Two central CSPs for which this question has been resolved
(assuming the unique games conjecture or at least that unique
games is hard) are 3-SAT and MAX CUT. For 3-SAT, guessing a
random assignment satisfies 7/8 of the constraints in
expectation and Johan Håstad's 3-bit PCP (probabilistically
checkable proof) shows that it is NP-hard to obtain a ratio
which is better than 7/8. For MAX CUT, the Goemans-Williamson
algorithm gives a .878 approximation ratio and the paper
"Optimal inapproximability results for
max-cut and other 2-variable CSPs?" by Subhash
Khot, Guy Kindler, Elchannan Mossel, and Ryan O'Donnell shows
that this algorithm is optimal (assuming that unique games is
hard) .
For general CSPs, Prasad Raghavendra showed in his breakthrough
paper "Optimal Algorithms and Inapproximability Results for
Every CSP?" that (assuming unique games is hard) the optimal
polynomial-time algorithm for any type of CSP is to use a
standard semidefinite program (SDP) followed by a rounding
scheme which rounds the output of the SDP into an actual
solution. However, determining which rounding scheme is optimal
may be extremely hard. In fact, it is not even known to be
decidable! For this reason, there is still much that is unknown
about the approximability of CSPs.
Papers:
- Separating MAX 2-AND, MAX DI-CUT and MAX CUT.
Joshua Brakensiek, Neng Huang, Aaron Potechin, and Uri
Zwick. FOCS 2023. arXiv
- On the Mysteries of MAX NAE-SAT. Joshua
Brakensiek, Neng Huang, Aaron Potechin, and Uri Zwick. SODA
2021. arXiv
- On the Approximability of Presidential Type
Predicates. Neng Huang and Aaron Potechin. APPROX
2020. arXiv
- On the approximation resistance of balanced linear
threshold functions. Aaron Potechin. STOC 2019. arXiv