Inapproximability of Unique Games in Fixed-Point Logic with Counting
share
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 (1/2, 1/3 + delta)-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.
READ FULL TEXT
