Inapproximability of Unique Games in Fixed-Point Logic with Counting

Jamie Tucker-Foltz

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). Formally, we prove lower bounds ag…