Approximating Constraint Satisfaction Problems Symmetrically
share
This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming 𝖯≠𝖭𝖯 and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that 𝖯≠𝖭𝖯. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all α > 0, there exists a positive integer q = poly(1/α) such that no there is no FPC-interpretation giving an α-approximation of Unique Games on a label set of size q.
READ FULL TEXT
