Jamie Tucker-Foltz - Inapproximability of Unique Games in Fixed-Point Logic with Counting

lmcs:9090 - Logical Methods in Computer Science, April 10, 2024, Volume 20, Issue 2 - https://doi.org/10.46298/lmcs-20(2:3)2024
Inapproximability of Unique Games in Fixed-Point Logic with CountingArticle

Authors: Jamie Tucker-Foltz ORCID

    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 FPC-inexpressibility 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 $\mathbb{F}_2$ 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.

    Volume: Volume 20, Issue 2
    Published on: April 10, 2024
    Accepted on: February 15, 2024
    Submitted on: February 16, 2022
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 673 times.
    This article's PDF has been downloaded 345 times.