Inapproximability of Unique Games in Fixed-Point Logic with Counting
Inapproximability of Unique Games in Fixed-Point Logic with Counting
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 …