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 against the accuracy of FPC-interpretations that map Unique Games instances (encoded as relational structures) to rational numbers giving the approximate fraction of constraints that can be satisfied. 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 FPCinexpressibility results are based on variants of the CFI -construction, ours is significantly different. We start with a graph of very large girth and label the edges with random affine vector spaces over F2 that determine the constraints in the two structures. Duplicator's strategy involves maintaining a partial isomorphism over a minimal tree that spans the pebbled vertices of the graph.
A Fibrational Tale of Operational Logical Relations: Pure, Effectful and Differential
Dagnino, Francesco;
2024-01-01
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). Formally, we prove lower bounds against the accuracy of FPC-interpretations that map Unique Games instances (encoded as relational structures) to rational numbers giving the approximate fraction of constraints that can be satisfied. 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 FPCinexpressibility results are based on variants of the CFI -construction, ours is significantly different. We start with a graph of very large girth and label the edges with random affine vector spaces over F2 that determine the constraints in the two structures. Duplicator's strategy involves maintaining a partial isomorphism over a minimal tree that spans the pebbled vertices of the graph.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
