Inapproximability of Unique Games in Fixed-Point Logic with Counting

Abstract

We study the extent to which it is possible to approximate the optimal value of a Unique Games instance in Fixed-Point Logic with Counting (FPC). We prove two new FPC- inexpressibility results for Unique Games: the existence of a ( \frac12,\frac13 + δ )-inapproximability gap, and inapproximability to within any constant factor. Previous recent work has established similar FPC-inapproximability results for a small handful of other problems. Our construction builds upon some of these ideas, but contains a novel technique. While most FPC-inexpressibility results are based on variants of the CFI-construction, ours is significantly different.

Locations

• arXiv (Cornell University) - View - PDF