*A conference version of this paper appeared in LICS 2021 under an identical title. ACM subject classification: Theory of computation / Logic / Finite Model Theory

# Inapproximability of Unique Games in Fixed-Point Logic with Counting

Jamie Tucker-Foltz  Harvard University<EMAIL_ADDRESS>
###### 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). 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.

###### Key words and phrases:

fixed-point logic with counting, descriptive complexity, unique games,
inapproximability, inexpressibility.

##  1\. Introduction

While the bulk of ordinary complexity theory rests on conjectures about the
limits of efficient computation (e.g., $\mathsf{P}\neq\mathsf{NP}$),
descriptive complexity has had much success in proving _unconditional_ lower
bounds. By restricting attention only to those algorithms that can be defined
in some given primitive logic, it is possible to say much more about what such
an algorithm is capable or incapable of doing.

One such logic is _Fixed-Point Logic with Counting (FPC)_ , which is first
order logic augmented with a least fixed point operator, numeric variables and
counting quantifiers asserting that a given number of distinct objects satisfy
a given predicate. The set of decision problems definable in FPC forms a
proper subset of $\mathsf{P}$.111In the presence of a relation interpreted as
a total order over the universe, these sets are equal by the Immerman-Vardi
Theorem [Imm86] [Var82], but this paper is concerned with unordered
structures. Roughly, a polynomial-time algorithm is definable as an FPC-
interpretation only if it respects the natural symmetries of its input,
without making any arbitrary choices that break those symmetries.222It is
difficult to rigorously define exactly what is meant by “symmetry breaking.”
Anderson and Dawar [AD17] give a precise result along these lines, defined in
terms of symmetric circuits. Thus, FPC has become an extremely important and
well-studied logic [Daw15], as it seems to elegantly capture the essence of
_symmetric computation_. It is a robust logic, including a wide range of
powerful algorithmic techniques, such as linear and semidefinite programming.

It was once thought that FPC captured all of polynomial-time, until Cai, Fürer
and Immerman [CFI89] constructed a problem that is solvable in polynomial-
time, yet not definable in FPC. Their proof technique, which has since become
known as a _CFI-construction_ , was to exhibit pairs of problem instances
$(\mathbb{A}_{1},\mathbb{B}_{1}),(\mathbb{A}_{2},\mathbb{B}_{2}),(\mathbb{A}_{3},\mathbb{B}_{3}),\dots$
such that each $\mathbb{A}_{k}$ is a YES instance, each $\mathbb{B}_{k}$ is a
NO instance, yet $\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ are indistinguishable
by any sentence of FPC of complexity $k$ (formally, they are
$C^{k}$-equivalent: Duplicator wins the $k$-pebble bijective game played on
$\mathbb{A}_{k}$ and $\mathbb{B}_{k}$; see Section 2.2 for the full
definition). CFI-constructions have been used to establish logical
inexpressibility results for a range of other decision problems—some solvable
in polynomial-time, others $\mathsf{NP}$-hard.

In a recent paper, Atserias and Dawar [AD19] adapted this technique to obtain
the first known _FPC-inapproximability_ results, proving the nonexistence of
FPC-definable approximation algorithms. Essentially, this requires that
$\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ not only have different optimal values,
but that these optimal values differ by some constant multiplicative factor.
Atserias and Dawar were able to construct such instances to derive a tight
FPC-inapproximability gap for 3XOR (like 3SAT but with XOR’s instead of OR’s
in each clause), which was then extended via first order reductions to yield
lower bounds for 3SAT, VertexCover and LabelCover.

###  1.1. Main results

In this paper, we extend this line of work to consider a keystone problem in
the theory of approximation algorithms: UniqueGames. A UniqueGames instance
$U$ is specified by a set of variables taking values in some fixed label set
$[q]=\\{1,2,\dots,q\\}$, and a set of constraints. Each constraint requires
that a certain pair of variables take values that are consistent with some
permutation on $[q]$. The goal is to find the maximum fraction of constraints
that can be simultaneously satisfied.333The UniqueGames problem is so named
because, given any value for one variable in a constraint, there is a unique
value for the other variable that satisfies the constraint (defined by the
permutation on the label set associated to the constraint). There is an
alternative interpretation of the optimization problem in terms of finding an
optimal strategy in a game between two provers and a verifier, where the
provers wish to convince the verifier that there is an assignment satisfying
all constraints. See the survey by Khot [Kho10] for more background on
UniqueGames. We denote this fraction by $\textup{opt}(U)$. Our main result
(Theorem 12) is that, for any $\delta>0$ and any positive integer $\ell$, for
sufficiently large $q$ we can construct pairs of UniqueGames instances
$(\mathbb{A}_{1},\mathbb{B}_{1}),(\mathbb{A}_{2},\mathbb{B}_{2}),(\mathbb{A}_{3},\mathbb{B}_{3}),\dots$
on a label set of size $q$ such that, for all $k$, $\mathbb{A}_{k}$ and
$\mathbb{B}_{k}$ are $C^{k}$-equivalent, yet

$\displaystyle\textup{opt}(\mathbb{A}_{k})\geq\frac{1}{2^{\ell}},$
$\displaystyle\textup{opt}(\mathbb{B}_{k})<\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta.$

There are two important specializations of the parameter $\ell$. Sending
$\ell\to\infty$, it follows that there is no constant-factor approximation
algorithm for UniqueGames that is definable as an FPC-interpretation
(Corollary 13). As discussed, this doesn’t rule out the existence of _any_
polynomial-time constant-factor approximation algorithm, but it does rule out
the existence of a _symmetric_ algorithm, including any algorithm based
primarily on linear or semidefinite programming.

Setting $\ell=1$, this result implies that no sentence of FPC can distinguish
instances of optimal value $\frac{1}{2}$ from instances of optimal value
$\frac{1}{3}+\delta$. The analogue of such a result in ordinary complexity
theory would be that UniqueGames has a _$(\frac{1}{2},\frac{1}{3}+\delta)$
-inapproximability gap_, i.e., assuming $\mathsf{P}\neq\mathsf{NP}$, there is
no polynomial-time algorithm distinguishing instances of optimal value
$\frac{1}{2}$ from instances of optimal value $\frac{1}{3}+\delta$. Our result
is, of course, logically incomparable to results of this kind since we have
imposed an FPC-definability requirement and dropped the assumption that
$\mathsf{P}\neq\mathsf{NP}$. If we were to compare them modulo this exchange
of assumptions, our result would be stronger than what was known prior to the
resolution of the 2-2 Games Conjecture in 2018.444The 2-2 Games Theorem
[KMS18] [DKK+18] implies a $(\frac{1}{2},\delta)$-inapproximability gap for
UniqueGames, while the previous best was $(\frac{1}{2},\frac{3}{8}+\delta)$
from 2012, due to O’Donnell and Wright [OW12]. However, while the 2-2 Games
Theorem is the culmination of over a decade of research spanning several
papers, our FPC lower bound is self-contained and qualitatively very
different, exploiting a peculiar weakness of FPC: the inability to perform
Gaussian elimination. The result is thus a testament to the power of
descriptive complexity in proving lower bounds for important restricted
classes of algorithms, even in the realm of approximation.

###  1.2. Connections to semidefinite programming

The prominence of UniqueGames as a problem of study in complexity theory is
primarily due to its deep connections with semidefinite programming. A famous
theorem of Raghavendra [Rag09] establishes that, for any constraint
satisfaction problem $\Lambda$, if we assume $\mathsf{P}\neq\mathsf{NP}$ and
the _Unique Games Conjecture (UGC)_ , the best polynomial-time approximation
algorithm for $\Lambda$ is given by solving and rounding a specific
semidefinite programming relaxation. Thus, proving the UGC would immediately
yield a complete classification of the approximability of constraint
satisfaction problems, with matching upper and lower bounds on the optimal
approximation ratio obtainable by any polynomial-time algorithm (conditional
on $\mathsf{P}\neq\mathsf{NP}$). Raghavendra’s theorem is established via a
general, abstract reduction from UniqueGames to $\Lambda$. As it so happens,
this reduction is definable as an FPC-interpretation. Together with the fact
that semidefinite programming is also FPC-definable [DW17], this implies an
analogue of Raghavendra’s result for algorithms that are definable in FPC,
holding without the assumption that $\mathsf{P}\neq\mathsf{NP}$ [TF20].

Thus, if we could prove an FPC-version of the UGC, we would have a complete
and unconditional understanding of the limits of symmetric computation in
approximating constraint satisfaction problems. This conjecture is as follows.

######  Conjecture 1 (FPC-UGC [TF20]).

For all $\varepsilon,\delta>0$, there exists $q$ such that there is no
sentence $\phi$ of FPC such that, for any UniqueGames instance $\mathbb{A}$ on
a label set of size $q$,

  1. (1)

if $\textup{opt}(\mathbb{A})\geq 1-\varepsilon$, then $\mathbb{A}\models\phi$,
and

  2. (2)

if $\textup{opt}(\mathbb{A})<\delta$, then $\mathbb{A}\not\models\phi$.

If true, this would also imply that no fixed level of the Lasserre hierarchy
can disprove the ordinary UGC, which is a well-known open problem in
complexity theory.555This problem is described in [KPS10]. See [DW17] for a
discussion of the relationship between FPC and the Lasserre hierarchy.

The main result of this paper is a step in the direction of proving this
conjecture. Instead of a $(1-\varepsilon,\delta)$-gap, we have a
$(\frac{1}{2^{\ell}},\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta)$-gap for any
positive integer $\ell$. In light of our aforementioned comparison to existing
conditional lower bounds on UniqueGames, we believe there is promise that the
FPC-UGC may be resolved before the ordinary UGC.

###  1.3. Challenges and techniques

In typical CFI-constructions, $\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ are
exactly the same except at one small place. The difference is critical in that
it causes $\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ to differ with respect to the
property being shown to be inexpressible, yet it is small enough that
Duplicator can repeatedly move it around to somewhere else, hiding it from
Spoiler. For UniqueGames (and probably any other optimization problem of
practical interest), two structures differing only on a small number of
constraints must have nearly the same optimal value. Since we require
instances whose optimal values differ significantly, this standard approach
does not work for our setting. Duplicator will never be able to maintain an
invariant that the two structures look isomorphic everywhere except in one
place.

Atserias and Dawar [AD19] overcame this difficulty for 3XOR by constructing a
3CNF Boolean formula from the 3XOR instance and applying theorems on
resolution proofs and their connection to existential pebble games. This
approach does not work for UniqueGames, since the variables are not Boolean,
and the constraints are only between pairs of variables, not triples. Thus,
our construction is quite different from existing CFI-constructions in the
literature.

The main idea is to start from a graph of large girth and label each edge with
a random $\ell$-dimensional subspace of $\mathbb{F}_{2}^{m}$ (the
$m$-dimensional vector space over the 2-element field) for some large integer
$m>\ell$. These subspaces determine the equations in the more-satisfiable
instance $\mathbb{A}_{k}$. To obtain the less-satisfiable instance
$\mathbb{B}_{k}$, we transform these subspaces into affine subspaces, shifted
by random vectors. Duplicator’s strategy in the $k$-pebble bijective game
relies on the fact that, with high probability, along _any_ path $p$ that is
sufficiently long (though less than the girth), the union of all of the
subspaces along $p$ spans $\mathbb{F}_{2}^{m}$. This can be used to “fill in”
the bijection between $\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ along long paths,
so all Duplicator has to worry about are short paths between pebbled vertices.
Duplicator can ensure consistency across these short paths by maintaining an
appropriate invariant throughout the game.

###  1.4. Organization

In Section 2 we review the necessary background on UniqueGames, FPC, and
approximation algorithms. In Section 3 we adapt a key tool from the literature
on CFI-constructions for satisfiability of systems of linear equations to our
setting. Section 4 works through two examples illustrating some of the main
ideas of our construction. The formal proof of $C^{k}$-equivalence is
presented in Section 5, and conclusions follow in Section 6.

##  2\. Preliminaries

We assume the reader is familiar with relational structures and first-order
(FO) logic. All graphs are undirected, but may contain multiple edges between
a pair of vertices and/or loops from a vertex to itself. A graph is _simple_
if it has no multiple edges or self-loops. Paths are not allowed to repeat
edges.

###  2.1. Unique games

We denote the maximization problem of UniqueGames on a label set of size $q$
by UG($q$). We view the label set as $[q]:=\\{1,2,\dots,q\\}$. We encode
UG($q$) instances as relational structures using a vocabulary
$\tau_{\textup{{UG}}(q)}$ consisting of $q!$ relation symbols, each of arity
2: for every permutation $\pi:[q]\to[q]$, $\tau_{\textup{{UG}}(q)}$ has a
relation symbol $P_{\pi}$. The universe is the set of variables, and each
$P_{\pi}$ is interpreted as the set of pairs of variables $(x_{1},x_{2})$ to
which we have a constraint that $x_{1}$ and $x_{2}$ should take values $z_{1}$
and $z_{2}$ in $[q]$ such that $\pi(z_{1})=z_{2}$. These are precisely the
kinds of constraints that are allowed in UniqueGames. For any UG($q$) instance
$U$, the objective is to compute $\textup{opt}(U)\in[0,1]$, the maximum
fraction of constraints that can be simultaneously satisfied by any assignment
of variables to values in $[q]$. We call $\textup{opt}(U)$ the _optimal value_
, or _satisfiability_ , of $U$.

Figure 1.  A UniqueGames instance over the label set $\\{1,2\\}$ represented
graphically, along with one optimal solution (green). Only the bottom edge
(red) is unsatisfied by this solution.

It is often convenient to think of UG($q$) instances as being defined over
some graph $H$, where each vertex $v\in V(H)$ represents a variable $x_{v}$,
and each edge $\\{v_{1},v_{2}\\}\in E(H)$ is associated to a permutation
$\pi_{v_{1},v_{2}}$ on the label set $[q]$ defining which labels for variable
$x_{v_{1}}$ correspond to which labels for variable $x_{v_{2}}$. When the
permutations are involutions (as will be the case throughout this paper), the
orientation of the edges does not matter, so we can associate each permutation
to an edge, rather than an ordered pair of vertices. For example, Figure 1
shows a UG(2) instance $U$ with edge permutations written in cycle notation,
along with one of the optimal assignments ($x_{v_{1}}=x_{v_{3}}=x_{v_{4}}=1$;
$x_{v_{2}}=2$) realizing $\textup{opt}(U)=\frac{3}{4}$. If we were to encode
this instance as a $\tau_{\textup{{UG}}(2)}$-structure

$\mathbb{A}=\langle A,P_{()}^{\mathbb{A}},P_{(12)}^{\mathbb{A}}\rangle,$

the universe would be $A=\\{x_{v_{1}},x_{v_{2}},x_{v_{3}},x_{v_{4}}\\}$, and
the relations would be interpreted as

$\displaystyle P_{()}^{\mathbb{A}}$
$\displaystyle=\\{(x_{v_{1}},x_{v_{3}}),(x_{v_{3}},x_{v_{1}})\\},$
$\displaystyle P_{(12)}^{\mathbb{A}}$
$\displaystyle=\\{(x_{v_{1}},x_{v_{2}}),(x_{v_{2}},x_{v_{1}}),(x_{v_{2}},x_{v_{4}}),(x_{v_{4}},x_{v_{2}}),(x_{v_{3}},x_{v_{4}}),(x_{v_{4}},x_{v_{3}})\\}.$

A special subclass of UniqueGames instances play a particularly important
role, both in this paper and in other papers on UniqueGames. We call these
GroupUniqueGames instances, which satisfy the following additional properties:

  1. (1)

The label set $[q]$ is identified with some finite Abelian group $A$ of order
$q$.

  2. (2)

For every edge permutation $\pi$, there is some $g\in A$ such that
$\pi(x)=g+x$ (we always write the group operation additively). Thus, we can
identify the set of edge permutations with $A$ as well.

It is convenient to express constraints as equations in $A$. For instance, if
$\pi$ is the permutation from condition (2) above and
$(x_{v_{1}},x_{v_{2}})\in P_{\pi}^{\mathbb{A}}$ for some
$\tau_{\textup{{UG}}(q)}$-structure $\mathbb{A}$, then we would write this
constraint as the equation

$x_{v_{2}}=g+x_{v_{1}}.$

We depict such a constraint graphically by drawing $g$ on the edge
$\\{v_{1},v_{2}\\}$ (see Figures 2 and 3 for example). Henceforth we will
informally speak of GroupUniqueGames instances $U$ and equations that occur as
constraints of $U$, with the implicit understanding of how these are formally
represented as $\tau_{\textup{{UG}}(q)}$-structures $\mathbb{A}$ and relations
$P_{\pi}^{\mathbb{A}}$.

###  2.2. The logics FPC and $C^{k}$

Since we are only concerned with lower bounds in this paper, it is not
necessary to go into the formal definition of FPC. All that we need is the
fact that, for any FPC sentence $\phi$, there is a number $k$ such that $\phi$
can be translated into $C^{k}$, the fragment of FO logic with counting
quantifiers consisting of (possibly infinite) sentences with only $k$
variables [Ott97]. Therefore, to show that a given property $\mathcal{P}$ is
not expressible in FPC, it suffices to construct, for any $k$, a pair of
structures $\mathbb{A}=\mathbb{A}_{k}$ and $\mathbb{B}=\mathbb{B}_{k}$ such
that $\mathbb{A}$ has property $\mathcal{P}$ but $\mathbb{B}$ does not, yet no
sentence of $C^{k}$ can distinguish $\mathbb{A}$ from $\mathbb{B}$, in the
sense that $\mathbb{A}$ models any $C^{k}$ sentence if and only if
$\mathbb{B}$ does. When this is the case, we say that $\mathbb{A}$ and
$\mathbb{B}$ are _$C^{k}$ -equivalent_, written
$\mathbb{A}\equiv_{C^{k}}\mathbb{B}$.

There is a useful characterization $C^{k}$-equivalence in terms of a game
between two players, Spoiler and Duplicator, called the _$k$ -pebble bijective
game_. The board on which they play consists of the universe $A$ of structure
$\mathbb{A}$ and the the universe $B$ of structure $\mathbb{B}$. There are $k$
pairs of _pebbles_ , initially not placed anywhere. Throughout the game, the
pairs of pebbles will be placed on elements of the two universes, one pebble
in each universe. Each round of the game consists of three parts:

  1. (1)

Spoiler picks up one of the $k$ pairs of pebbles, removing them from the
board.

  2. (2)

Duplicator gives a bijection $f:A\to B$ such that, for all $1\leq i\leq k$, if
the $i^{\text{th}}$ pebble pair is placed on some pair of elements $a_{i}\in
A$, $b_{i}\in B$, then $f(a_{i})=b_{i}$.

  3. (3)

Spoiler places the pebbles back down, placing one pebble on some $a\in A$ and
the other pebble on $f(a)\in B$.

At the end of a round, Spoiler wins if the map sending each pebbled element in
$A$ to its correspondingly-pebbled element in $B$ is not a _partial
isomorphism_ between the two structures, i.e., there is some relation in one
of the two structures that holds of a set of pebbled elements, but the
corresponding relation does not hold in the other structure of the
correspondingly-pebbled elements. If Spoiler is unable to win the game in any
finite number of moves, then Duplicator wins.

[[Hel96]] Duplicator has a winning strategy in the $k$-pebble bijective game
played on $\mathbb{A}$ and $\mathbb{B}$ if and only if
$\mathbb{A}\equiv_{C^{k}}\mathbb{B}$.

###  2.3. Definability of algorithms

Any algorithm defines a mapping from inputs to outputs. Suppose we fix finite,
relational vocabularies $\sigma$ for the input type and $\tau$ for the output
type. By saying that an algorithm is _FPC-definable_ , we mean that the
mapping from $\sigma$-structures to $\tau$-structures defined by the algorithm
can be realized as an _FPC-interpretation of $\tau$ in $\sigma$_.

Roughly, an FPC-interpretation of $\tau$ in $\sigma$ is a formal way to
construct a $\tau$-structure $\mathbb{B}$ from a $\sigma$-structure
$\mathbb{A}$ by defining the universe of $\mathbb{B}$ in terms of copies of
the universe of $\mathbb{A}$, with FPC $\sigma$-formulas defining membership
for each relation in $\tau$. For the formal details, see, for example, Dawar
and Wang [DW17]. Theorem 6 of [DW17] contains an example of an FPC-definable
algorithm.

###  2.4. Inapproximability

Let $\Lambda$ denote an arbitrary maximization problem (e.g., think of
$\Lambda$ as UG($q$) for some $q$). For $\alpha\in[0,1]$, an _$\alpha$
-approximation algorithm_ for $\Lambda$ is a polynomial-time algorithm that,
given an instance of $\Lambda$ with optimal value $x^{*}$, returns a value $x$
such that $\alpha x^{*}\leq x\leq x^{*}$. Typically, an $\alpha$-approximation
algorithm works by finding a valid “solution” to the instance of $\Lambda$
(for UniqueGames, this would be an assignment of variables) and returning the
value of that solution. The solution may not be optimal, but it should be
guaranteed to have value at least an $\alpha$-fraction of that of the optimal
solution, whatever that value may be. The closer $\alpha$ is to 1, the better
the guarantee of algorithm.

Let us fix vocabularies $\tau_{\Lambda}$ for instances of $\Lambda$ and
$\tau_{\mathbb{Q}}$ for rational numbers, so that an FPC-definable
approximation algorithm for $\Lambda$ is an FPC-interpretation of
$\tau_{\mathbb{Q}}$ in $\tau_{\Lambda}$. The following lemma is a logical
formulation of the well-known relationship between approximation algorithms
and gap problems.

######  Lemma 2.

Suppose, for some rational numbers $c\geq s\geq 0$, no sentence of FPC can
distinguish $\tau_{\Lambda}$ structures with optimal value $\geq c$ from those
with optimal value $<s$. Then there is no FPC-definable $\alpha$-approximation
algorithm for $\Lambda$ for any $\alpha\geq\frac{s}{c}$.

######  Proof 2.1.

We prove the contrapositive. Suppose there was such an interpretation $\Theta$
of $\tau_{\mathbb{Q}}$ in $\tau_{\Lambda}$. Then we can use $\Theta$ to write
an FPC sentence $\phi$ in vocabulary $\tau_{\Lambda}$ expressing the property
that, for a given $\tau_{\Lambda}$ structure $\mathbb{A}$,
$\Theta(\mathbb{A})\geq s$. Let $\mathbb{A}$ be any $\tau_{\Lambda}$ structure
with optimal value $x^{*}$ such that either

  1. (1)

$x^{*}\geq c$, or

  2. (2)

$x^{*}<s$.

Let $x:=\Theta(\mathbb{A})$. If $\mathbb{A}\models\phi$, we have $x^{*}\geq
x\geq s$. Therefore, we cannot be in case (2), so we must be in case (1).
Conversely, if $\mathbb{A}\not\models\phi$, we have

$\alpha x^{*}\leq x<s\leq c\alpha.$

Therefore, $x^{*}<c$, so we cannot possibly be in case (1), and hence must be
in case (2). Thus, $\phi$ distinguishes the two cases.

So, just as in ordinary complexity theory, where hardness of a gap problem
(that is, distinguishing the two cases in Lemma 2), implies hardness of
approximation, FPC-inexpressibility of a gap problem implies the nonexistence
of FPC-definable approximation algorithms. In either case, the goal in proving
lower bounds is always to establish as wide a gap as possible.

##  3\. The label-lifted instance

Let $U$ be a GroupUniqueGames instance with group $A$ and variable set

$\\{x_{v}\ |\ v\in V\\}.$

Then we define $\mathcal{G}(U)$ to be a GroupUniqueGames instance with group
$A$ and variable set

$\\{x_{v}^{g}\ |\ v\in V,\ g\in A\\}.$

For every equation

$x_{v_{1}}-x_{v_{2}}=z$

in the constraint set of $U$ and every $g_{1},g_{2}\in A$, we have the
equation

$(x_{v_{1}}^{g_{1}}-g_{1})-(x_{v_{2}}^{g_{2}}-g_{2})=z$

in the constraint set of $\mathcal{G}(U)$. We call $\mathcal{G}(U)$ the
_label-lifted instance 666This construction is similar to the _label-extended
graph_ of a UniqueGames instance (see, for example, [Kol11, GT18]), but it is
not the same thing. The label extended-graph is obtained by taking all of the
edges with identity constraints in the label-lifted instance.  of $U$_.

The operator $\mathcal{G}$ is similar to the operator $G$ used by Atserias and
Dawar [AD19, Sec. 3.2], and also implicitly used by Atserias, Bulatov and
Dawar [ABD09, Sec. 3]. The hope is that it is easier for Duplicator to win the
$k$-pebble bijective game played on $\mathcal{G}(U_{1})$ and
$\mathcal{G}(U_{2})$ than on the original pair $U_{1}$ and $U_{2}$, while at
the same time, applying $\mathcal{G}$ does not change the satisfiability.

######  Lemma 3.

For any GroupUniqueGames instance $U$,
$\textup{opt}(\mathcal{G}(U))=\textup{opt}(U)$.

######  Proof 3.1.

We begin by introducing some notation which is not used outside of this proof.
Suppose $U$ has $n$ variables, denoted $x_{v_{1}},x_{v_{2}},\dots,x_{v_{n}}$,
$C$ constraints, and there are $q$ group elements. For every $i,j\in[n]$,
write $c(i,j)$ for the number of constraints between variables $x_{v_{i}}$ and
$x_{v_{j}}$, and enumerate them as

$\\{x_{v_{i}}-x_{v_{j}}=z_{i,j,k}\ |\ k\in[c(i,j)]\\}.$

In the context of some fixed assignment of variables, for any constraint
equation $\beta$ let $\mathbb{I}(\beta)$ be the function that evaluates to 1
if $\beta$ is satisfied under the assignment and 0 if $\beta$ is not
satisfied.

Let $x_{v}$ be an assignment777We sometimes use a symbol like $x_{v}$ or
$x_{v}^{g}$ to denote a specific variable, and sometimes to denote the value
assigned to that variable. When $v$ is unspecified, as it is here, we mean a
function assigning a value to each variable. It should be clear from context
which of the three meanings we intend.  of variables attaining the optimum
satisfiability of $U$, i.e.,

$\textup{opt}(U)=\frac{1}{C}\sum_{i,j\in[n]}\
\sum_{k\in[c(i,j)]}\mathbb{I}(x_{v_{i}}-x_{v_{j}}=z_{i,j,k}).$

From this, define an assignment of variables of $\mathcal{G}(U)$ by

$x_{v}^{g}:=x_{v}+g.$

Then the optimal value of $\mathcal{G}(U)$ is at least the number of
constraints satisfied by this assignment divided by the total number of
constraints $\frac{1}{Cq^{2}}$, i.e.,

$\displaystyle\textup{opt}(\mathcal{G}(U))$
$\displaystyle\geq\frac{1}{Cq^{2}}\sum_{i,j\in[n]}\ \sum_{g_{i},g_{j}\in A}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})$
$\displaystyle=\frac{1}{Cq^{2}}\sum_{i,j\in[n]}\ \sum_{g_{i},g_{j}\in A}\
\sum_{k\in[c(i,j)]}\mathbb{I}(((x_{v_{i}}+g_{i})-g_{i})-((x_{v_{j}}+g_{j})-g_{j})=z_{i,j,k})$
$\displaystyle=\frac{1}{Cq^{2}}\sum_{i,j\in[n]}\ \sum_{g_{i},g_{j}\in A}\
\sum_{k\in[c(i,j)]}\mathbb{I}(x_{v_{i}}-x_{v_{j}}=z_{i,j,k})$
$\displaystyle=\frac{1}{Cq^{2}}\sum_{i,j\in[n]}(q^{2})\sum_{k\in[c(i,j)]}\mathbb{I}(x_{v_{i}}-x_{v_{j}}=z_{i,j,k})$
$\displaystyle=\frac{1}{C}\sum_{i,j\in[n]}\sum_{k\in[c(i,j)]}\mathbb{I}(x_{v_{i}}-x_{v_{j}}=z_{i,j,k})$
$\displaystyle=\textup{opt}(U).$

For the other direction, let $x_{v}^{g}$ be an assignment of variables
attaining the optimum satisfiability of $\mathcal{G}(U)$. Then

$\displaystyle\textup{opt}(\mathcal{G}(U))$
$\displaystyle=\frac{1}{Cq^{2}}\sum_{i,j\in[n]}\ \sum_{g_{i},g_{j}\in A}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})$
$\displaystyle=\frac{1}{Cq^{n}}\sum_{i,j\in[n]}\
\sum_{{g}_{1}{,}{g}_{2}{,}\dots,{g}_{n}\in A}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k}),$

since, for every fixed $i,j\in[n]$, the term

$\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})$

is counted exactly $q^{n-2}$ times. Rearranging the order of summation, we
have

$\textup{opt}(\mathcal{G}(U))=\frac{1}{Cq^{n}}\sum_{{g}_{1}{,}{g}_{2}{,}\dots,{g}_{n}\in
A}\ \sum_{i,j\in[n]}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})$
(1)

By the averaging principle, there must be some fixed
${g}_{1}{,}{g}_{2}{,}\dots,{g}_{n}\in A$ such that

$\sum_{i,j\in[n]}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})\geq
C\cdot\textup{opt}(\mathcal{G}(U)),$ (2)

for otherwise, if all of the $q^{n}$ choices of
${g}_{1}{,}{g}_{2}{,}\dots,{g}_{n}\in A$ failed to satisfy (2), we could
strictly upper-bound the right-hand side of (1) by

$\frac{1}{Cq^{n}}(q^{n})\left(C\cdot\textup{opt}(\mathcal{G}(U))\right)=\textup{opt}(\mathcal{G}(U)),$

contradicting (1). Using these fixed $g_{i}$ values, we define an assignment
of variables of $U$ by

$x_{v_{i}}:=x_{v_{i}}^{g_{i}}-g_{i}.$

It then follows that the optimal value of $U$ is at least the fraction of
constraints satisfied by this assignment, i.e.,

$\displaystyle\textup{opt}(U)$ $\displaystyle\geq\frac{1}{C}\sum_{i,j\in[n]}\
\sum_{k\in[c(i,j)]}\mathbb{I}(x_{v_{i}}-x_{v_{j}}=z_{i,j,k})$
$\displaystyle=\frac{1}{C}\sum_{i,j\in[n]}\
\sum_{k\in[c(i,j)]}\mathbb{I}((x_{v_{i}}^{g_{i}}-g_{i})-(x_{v_{j}}^{g_{j}}-g_{j})=z_{i,j,k})$
$\displaystyle\geq\textup{opt}(\mathcal{G}(U))\ \ \ \ \ \text{(by
(\ref{equGSameSatisfiability2}))},$

as desired.888We remark that, with very slight modification, this argument
also shows that the $G$ operator of Atserias and Dawar [AD19] preserves the
exact satisfiability of a 3XOR instance. In other words, part (2) of Lemma 3
of [AD19] can be strengthened, and as a consequence, the third paragraph in
the proof of Lemma 4 of [AD19] is unnecessary.

##  4\. Examples

Before presenting the general gap construction in the next section, we first
describe some special cases: pairs of $C^{k}$-equivalent unique games
instances with different optimal values, for $k\in\\{2,3\\}$.

###  4.1. An example where $k=2$

The label-lifted instance is useful for Duplicator since it makes any two
GroupUniqueGames instances on the same underlying graph (in the sense of
Section 2.1) locally isomorphic. For example, take $U_{1}$ and $U_{2}$ to be
as in Figure 2.

Figure 2.  Two GroupUniqueGames instances $U_{1}$ and $U_{2}$ with group
$\mathbb{F}_{2}$, and Duplicator’s bijection at some stage in the $k$-pebble
bijective game between $\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$, just
after Spoiler has picked up a pair of pebbles.

For both $U_{1}$ and $U_{2}$, the underlying graph $H$ is the complete graph
on 3 vertices. The group is $A:=\mathbb{F}_{2}$ (the finite field of two
elements, $\\{0,1\\}$, under addition modulo 2), so there are only two kinds
of constraints. The identity constraints are drawn in green and the non-
identity constraints are drawn in red. Instance $U_{1}$ has only identity
constraints, so is completely satisfiable by setting all variables to be the
same value. In $U_{2}$, the 3 constraints are inconsistent, but any 2 of them
can be satisfied, so the optimal value is $\frac{2}{3}$. Therefore, by Lemma
3, $\textup{opt}(\mathcal{G}(U_{1}))=1$ and
$\textup{opt}(\mathcal{G}(U_{2}))=\frac{2}{3}$. However, $\mathcal{G}(U_{1})$
and $\mathcal{G}(U_{2})$ are $C^{2}$-equivalent. Let $X$ denote the common
variable set of both instances. Duplicator’s strategy in the 2-pebble
bijective game is to always give a bijection $f:X\to X$ (from the universe of
$\mathcal{G}(U_{1})$ to the universe of $\mathcal{G}(U_{2})$) with the
following property:

For all $v\in V(H)$, there exists $g^{*}(v)\in A$ such that, for any $g\in A$,
$f(x_{v}^{g})=x_{v}^{g+g^{*}(v)}$. (3)

So, in any given round, Duplicator’s bijection is completely determined by a
map $g^{*}:V(H)\to A$. If there is one pebble pair on the board on
$(x_{v}^{g_{1}},x_{v}^{g_{2}})$, as there is in Figure 2, then for each
neighbor $u$ of $v$ in $H$, $g^{*}(u)$ is uniquely determined to be the value
which makes the bijection $f$ an isomorphism across all constraints involving
vertices $u$ and $v$. In the figure, $g^{*}(u)=1\in\mathbb{F}_{2}$ and
$g^{*}(v)=g^{*}(w)=0$. The bijection $f$ is depicted by the blue dotted lines;
notice the swap at the vertices involving $u$ corresponding to $g^{*}(u)=1$.
No matter which of the six locations Spoiler places the pebble pair, one can
verify that any relations between two pebbled vertices will be of the same
kind.

We do not go into the general proof, but this strategy enables Duplicator to
win the 2-pebble bijective game between $\mathcal{G}(U_{1})$ and
$\mathcal{G}(U_{2})$ as long as $U_{1}$ and $U_{2}$ are defined over the same
underlying graph, and this graph is simple. It is possible to construct
GroupUniqueGames instances $U_{2}$ over simple graphs with arbitrarily low
satisfiability $\delta>0$. Turning all constraints into identity constraints,
we can then obtain $U_{1}$ such that $\textup{opt}(\mathcal{G}(U_{1}))=1$,
$\textup{opt}(\mathcal{G}(U_{2}))=\delta$, but
$\mathcal{G}(U_{1})\equiv_{C^{2}}\mathcal{G}(U_{2})$. Thus, for $k=2$, the
objective has been accomplished: we have a $(1,\delta)$-inapproximability gap
for $C^{2}$-definable algorithms, for arbitrarily low $\delta$.

###  4.2. The challenge of $k\geq 3$

To extend this result to an inapproximability gap for FPC-definable
algorithms, we need $C^{k}$-equivalence for all $k$. Unfortunately, we hit a
fundamental barrier starting at $k=3$:

######  Proposition 4.

For any positive integer $q$, there is an FPC sentence $\phi$ expressing the
property that a $\textup{{{UG}}}(q)$ instance (encoded as a
$\tau_{\textup{{UG}}(q)}$-structure) is completely satisfiable. Furthermore,
$\phi$ can be converted into a $C^{3}$ sentence.

######  Proof 4.1.

For each fixed label $i\in[q]$, in the context of a free variable $x$, we
define $q$ unary relations $U_{i,1},U_{i,2},\dots,U_{i,q}$ by simultaneous
induction:

$\displaystyle U_{i,i}(y)$ $\displaystyle\impliedby(x=y)$ $\displaystyle
U_{i,j}(y)$ $\displaystyle\impliedby\exists
z\bigvee_{\pi:[q]\to[q]}\left(P_{\pi}(y,z)\wedge U_{i,\pi(j)}(z)\right)$

The meaning of $U_{i,j}(y)$ is that, _given $x$ has label $i$, it is implied
by the constraints that $y$ has label $j$_. Thus, $U_{i,i}(x)$ is defined to
be true, and whenever a constraint $P_{\pi}$ holds on a pair of elements
$(y,z)$ and we know what the label of $z$ must be, we inductively derive what
the label of $y$ must be. We claim that the following sentence expresses the
property that a $\textup{{{UG}}}(q)$ instance is completely satisfiable:

$\phi\equiv\forall x\bigvee_{i\in[q]}\bigwedge_{\begin{subarray}{c}j\in[q]\\\
j\neq i\end{subarray}}\neg U_{i,j}(x)$

The correctness of this formula relies on the observation that a UniqueGames
instance is _not_ completely satisfiable if and only if there exists an
inconsistent cycle of constraints, forcing some variable $x$ to be assigned
two different values. If $f$ is a satisfying assignment, then picking $i=f(x)$
must satisfy $\phi$. Conversely, if $\phi$ is satisfied, one can obtain a
satisfying assignment by picking one $x$ from each connected component of the
underlying graph and one satisfying witness $i$, then assigning labels to
every $y$ in that component by taking the unique $j$ such that $U_{i,j}(y)$
holds. (It is not too hard to see that the component being connected implies
$j$ exists, and $\phi$ being satisfied implies $j$ is unique).

Using the _Bekic principle_ [AN01, Lemma 1.4.2] [Lib04, Lemma 10.9], the
simultaneous inductions can be nested within each other in a way that reuses
variable names, resulting in least fixed-point (LFP) formulas for each of the
$q$ relations, still using only 3 variables ($x$, $y$ and $z$). Thus, $\phi$
can indeed be formally written as an LFP sentence, which is an FPC sentence.
Finally, $\phi$ can be translated into a $C^{3}$ sentence by unwrapping the
inductive definitions into infinite disjunctions, which again does not require
any additional variables.

This implies that there does not exist an FPC-inapproximability gap of
$(1,\delta)$ for any $\delta<1$ (this is sometimes referred to as “perfect
completeness”), since $\phi$ distinguishes an instance of optimal value 1 from
an instance of optimal value less than 1. In terms of the 3-pebble bijective
game, Spoiler’s winning strategy is to drop the first pebble pair anywhere,
then use the other two pebble pairs to traverse an inconsistent cycle of
constraints in the unsatisfiable instance.

###  4.3. An example where $k=3$

From Duplicator’s perspective, this difficulty stems from the fact that the
$g^{*}$ map from (3) is uniquely defined from neighboring vertices. To
circumvent this obstacle and give Duplicator more choices, we place a _bundle_
of parallel constraints between some pairs of variables. Unfortunately, this
comes with a price: since at most one constraint from each bundle can be
satisfied, we will necessarily have $\textup{opt}(\mathcal{G}(U_{1}))<1$.
Notice how this avoids the perfect completeness issue from Proposition 4.

Figure 3 shows an example of the parallel constraint method where the
underlying graph is $H:=K_{4}$. The group used is the additive part of
$\mathbb{F}_{2}^{2}$, the 2-dimensional vector space over the 2-element field.
We denote its elements as binary strings $\\{00,01,10,11\\}$, so that the
group operation is bitwise XOR.

Figure 3. Two GroupUniqueGames instances $U_{1}$ and $U_{2}$ of different
optimal values such that $\mathcal{G}(U_{1})\equiv_{C^{3}}\mathcal{G}(U_{2})$.
The constraints differ only on the bottom two edges.

Since the constraints of $U_{1}$ come in inconsistent pairs, at most half of
them can be satisfied. This upper bound is attainable by assigning all
variables to be $00$. Thus, $\textup{opt}(U_{1})=\frac{1}{2}$. On the other
hand, this assigment satisfies only $\frac{5}{12}$ of the edges in $U_{2}$,
and indeed, it can be verified by exhaustive search that
$\textup{opt}(U_{2})=\frac{5}{12}$.

Duplicator will follow a similar strategy as in the previous example. Suppose
that, at some stage in the 3-pebble bijective game played on
$\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$, there are two pebble pairs
already on the board, on variables involving vertices $v_{1}$ and $v_{3}$, and
Spoiler has just picked up the third pebble pair. This means that
$g^{*}(v_{1})$ and $g^{*}(v_{3})$ are already determined, so Duplicator just
needs to fill in $g^{*}(v_{2})$ and $g^{*}(v_{4})$. Let us discuss how
Duplicator determines $g^{*}(v_{4})$.

Duplicator will set $g^{*}(v_{4})$ so that the map

$f(x_{v}^{g}):=x_{v}^{g+g^{*}(v)}$

is a partial isomorphism among constraints involving $v_{4}$ and either
$v_{1}$ or $v_{3}$. (In particular, this will ensure $f$ is a partial
isomorphism between the pebbled variables if Spoiler places the pebble pair
down on variables involving $v_{4}$.) For the constraints involving $v_{3}$
and $v_{4}$, $f$ will be a partial isomorphism if, for any
$g_{3},g_{4}\in\mathbb{F}_{2}^{2}$, the following double implication holds:

$\displaystyle x_{v_{3}}^{g_{3}}-x_{v_{4}}^{g_{4}}=z$ $\displaystyle\text{ is
an equation in }\mathcal{G}(U_{1})$ $\displaystyle\iff
f(x_{v_{3}}^{g_{3}})-f(x_{v_{4}}^{g_{4}})=z$ $\displaystyle\text{ is an
equation in }\mathcal{G}(U_{2}).$

Expanding out the definitions of $f$ and $\mathcal{G}$, we can rewrite this
condition as

$\displaystyle(x_{v_{3}}+g_{3})-(x_{v_{4}}+g_{4})=z$ $\displaystyle\text{ is
an equation in }U_{1}$
$\displaystyle\iff(x_{v_{3}}+g_{3}+g^{*}(v_{3}))-(x_{v_{4}}+g_{4}+g^{*}(v_{4}))=z$
$\displaystyle\text{ is an equation in }U_{2}.$

Rearranging equations, and using the fact that the equations in $U_{2}$
between $x_{v_{3}}$ and $x_{v_{4}}$ are precisely the same equations in
$U_{1}$ plus a difference of $10$, this becomes

$\displaystyle x_{v_{3}}-x_{v_{4}}=z-g_{3}+g_{4}$ $\displaystyle\text{ is an
equation in }U_{1}$ $\displaystyle\iff
x_{v_{3}}-x_{v_{4}}=z-g_{3}+g_{4}-g^{*}(v_{3})+g^{*}(v_{4})+10$
$\displaystyle\text{ is an equation in }U_{1}.$

Notice that, in $U_{1}$, two equations of the form $x_{v_{3}}-x_{v_{4}}=z_{1}$
and $x_{v_{3}}-x_{v_{4}}=z_{2}$ both appear as constraints or both do not
appear as constraints if and only if $z_{1}$ and $z_{2}$ are the same, or
differ by $01$. Thus, $f$ is a partial isomorphism for constraints involving
$v_{3}$ and $v_{4}$ if and only if

$g^{*}(v_{4})-g^{*}(v_{3})+10\in\\{00,01\\}.$

By an analogous argument, one can derive that $f$ is a partial isomorphism for
constraints involving $v_{1}$ and $v_{4}$ if and only if

$g^{*}(v_{4})-g^{*}(v_{1})\in\\{00,11\\}.$

These two constraints on $g^{*}(v_{4})$ can be written as a system of 2
equations with 2 unknowns. The system always has a solution since $01$ and
$11$ are linearly independent. Thus, no matter what $g^{*}(v_{1})$ and
$g^{*}(v_{3})$ are, we have seen that Duplicator can find a value for
$g^{*}(v_{4})$ making $f$ an isomorphism over all constraints along the path
$(v_{1},v_{4},v_{3})$. For example, if $g^{*}(v_{3})=00$ and
$g^{*}(v_{1})=01$, then we set $g^{*}(v_{4})=10$. Duplicator can use the same
process to find a value for $g^{*}(v_{2})$ making $f$ an isomorphism over the
path $(v_{1},v_{2},v_{3})$.

##  5\. Proof of FPC-inapproximability gap

In comparison to the previous example, the general construction replaces
$\mathbb{F}_{2}^{2}$ with $\mathbb{F}_{2}^{m}$, with a bundle of $2^{\ell}$
constraints between every pair of adjacent vertices, for integers $0<\ell<m$.
A key difference is that it is no longer possible to make $f$ an isomorphism
over an arbitrary path of length 2 (such as $(v_{1},v_{4},v_{3})$ in the
example). However, we are able to show that there exists some $r$ such that it
is possible to make any path of length $r$ consistent (see Lemma 10). This
allows Duplicator to win as long as the base graph $H$ has suitably high
girth.

###  5.1. Construction

Our construction takes three parameters: $\varepsilon\in(0,\frac{1}{2})$,
$\delta>0$, and a positive integer $\ell$. Note that $\delta$ and $\ell$
affect the satisfiability of the GroupUniqueGames instances produced, whereas
$\varepsilon$ is an arbitrary constant that could just as well be fixed at
$\frac{1}{4}$. The construction is probabilistic, failing with probability at
most $2\varepsilon$. We let

$d:=2^{\ell}+1$ (4)

and

$\gamma:=1-\frac{\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\frac{\delta}{2^{\ell}}\right)}{\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta\right)}.$
(5)

Note that $\gamma>0$. Next, we pick

$m:=\left\lceil\frac{1}{\delta}+\left(\frac{2}{\delta
d}+1\right)\ell-\frac{2}{\delta d}\log_{2}(\varepsilon)\right\rceil,$ (6)

and finally,

$r:=\left\lceil\frac{2^{m\ell+1}(d^{m-\ell}-1)}{\gamma\varepsilon}\right\rceil+1.$
(7)

The GroupUniqueGames instances we construct all have the additive part of the
vector space $\mathbb{F}_{2}^{m}$ as the group, so $q:=2^{m}$. The parameters
above are chosen so that $\mathbb{B}_{k}=\mathcal{G}(U_{2})$ will be highly
unsatisfiable with high probability.

For any $k$, let $\widetilde{H}=\widetilde{H}_{k}$ be a $d$-regular simple
graph of girth at least $(k+1)^{2}r$. (Regular graphs of arbitrarily high
girth and degree are known to exist; see Lazebnik, Ustimenko and Woldar
[LUW94], for example.) For every edge $\\{v_{1},v_{2}\\}\in E(\widetilde{H})$,
independently choose a uniformly random vector
$b(v_{1},v_{2})=b(v_{2},v_{1})\in\mathbb{F}_{2}^{m}$ and a uniformly random
$\ell$-dimensional subspace999What this means is, randomly choose a set of
$\ell$ linearly independent vectors and take the span. Choose the first vector
uniformly at random from $\mathbb{F}_{2}^{m}\setminus\\{0\\}$, then choose
each subsequent vector uniformly at random from the subset of
$\mathbb{F}_{2}^{m}$ that is not in the span of the previously chosen vectors.
$Z(v_{1},v_{2})=Z(v_{2},v_{1})\subseteq\mathbb{F}_{2}^{m}$. Say that an edge
$e\in E(\widetilde{H})$ is _good_ if, for all paths
$(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{r})$ of length $r$ such that
$e=\\{v_{0},v_{1}\\}$, the set

$\bigcup_{1\leq i\leq r}Z(v_{i-1},v_{i})$

spans $\mathbb{F}_{2}^{m}$. Edges of $\widetilde{H}$ which are not good edges
are called _bad_ edges. We will shortly argue that, with high probability,
nearly all edges are good edges.

Let $H=H_{k}$ be the graph with vertex set $V(H):=V(\widetilde{H})$ and edge
set

$E(H):=\\{e\in E(\widetilde{H})\ |\ \text{$e$ is a good edge}\\}.$

We define GroupUniqueGames instances $U_{1}$, $\widetilde{U}_{1}$, $U_{2}$ and
$\widetilde{U}_{2}$ using the additive group structure on
$\mathbb{F}_{2}^{m}$. The variable sets of all four instances are

$\\{x_{v}\ |\ v\in V(H)\\}.$

For every edge $\\{v_{1},v_{2}\\}\in E(\widetilde{H})$, $\widetilde{U}_{1}$
and $\widetilde{U}_{2}$ have a bundle of $2^{\ell}$ constraints between the
corresponding variables. In $\widetilde{U}_{1}$, the constraints are

$\\{x_{v_{1}}-x_{v_{2}}=z\ |\ z\in Z(v_{1},v_{2})\\},$

whereas in $\widetilde{U}_{2}$, the constraints are

$\\{x_{v_{1}}-x_{v_{2}}=z+b(v_{1},v_{2})\ |\ z\in Z(v_{1},v_{2})\\}.$

Finally, $U_{1}$ and $U_{2}$ are obtained from $\widetilde{U}_{1}$ and
$\widetilde{U}_{2}$ by removing all constraints on pairs of variables
corresponding to bad edges, i.e., with constraints defined in the exact same
way as $\widetilde{U}_{1}$ and $\widetilde{U}_{2}$, but only for edges
$\\{v_{1},v_{2}\\}\in E(H)$. Our pair of $C^{k}$-equivalent instances will be
$\mathbb{A}_{k}:=\mathcal{G}(U_{1})$, and
$\mathbb{B}_{k}:=\mathcal{G}(U_{2})$.

The example from Section 4.3 is a special case of this construction where
$k:=3$, $H:=K_{4}$, $m:=2$, $\ell:=1$, and $r:=2$. The 1-dimensional
$Z$-subspaces consisted of the vectors drawn between each edge in $U_{1}$ in
Figure 3, with $b(v_{3},v_{4}):=10$ and all other $b$ vectors $00$.

###  5.2. Satisfiability properties

In the next section we prove that $\mathcal{G}(U_{1})$ and
$\mathcal{G}(U_{2})$ are always $C^{k}$-equivalent. But first, we now analyze
the optimal values of these two instances.

######  Lemma 5.

The satisfiability of $U_{1}$ (and thus of $\mathcal{G}(U_{1})$) is exactly
$\frac{1}{2^{\ell}}$.

######  Proof 5.1.

Since the constraints in each bundle of $U_{1}$ are pairwise incompatible with
each other, at most one constraint can be satisfied from each bundle, so the
total satisfiability is at most the bundle size $\frac{1}{2^{\ell}}$. The
assignment $x_{v}:=0$ attains this bound by satisfying the $z=0$ constraint in
each bundle (every subspace $Z(v_{1},v_{2})$ must contain $z=0$). The claim
about $\mathcal{G}(U_{1})$ follows from Lemma 3.

We next argue that, with high probability, $\mathcal{G}(U_{2})$ has a
significantly lower optimal value. The analysis requires many steps, so we
break the proof up over several lemmas. Say that a bundle of constraints is
“satisfied” if at least one constraint in the bundle is satisfied. We begin by
showing in Lemma 7 that, with high probability, most edges of $\widetilde{H}$
are good edges, in which case the satisfiability of $\widetilde{U}_{2}$
closely approximates the satisfiability of $U_{2}$. To analyze the expected
satisfiability of $\widetilde{U}_{2}$, in Lemma 8 we observe that any
assignment satisfying significantly more than a

$\frac{1}{2^{2\ell-1}+2^{\ell-1}}=\frac{1}{2^{\ell}}\cdot\frac{2}{d}$

fraction of constraints must completely satisfy all of the bundles over some
subgraph of $\widetilde{H}$ containing significantly more than a
$\frac{2}{d}$-fraction of the edges of $\widetilde{H}$. Such a subgraph must
necessarily contain many more edges than vertices, so it is highly improbable
that a random assignment will completely satisfy it. We then apply a union
bound over all assignments and all subgraphs to conclude that, with high
probability, no assignment satisfies more than a
$\frac{1}{2^{2\ell-1}+2^{\ell-1}}$ fraction of constraints.

######  Lemma 6.

For any $d\geq 3$ and positive integer $n$,

$\frac{d^{n}-d^{n-1}}{(d-1)^{n}}+d^{n-1}-1\leq\frac{d^{n}-1}{d-1}.$

######  Proof 5.2.

When $n=1$, both sides are 1. When $n=2$, the inequality reads

$\frac{d}{d-1}+d-1\leq d+1,$

which is clearly true for $d\geq 3$. So assume $n\geq 3$. Then, using the fact
that $d\geq 3$, we have

$\displaystyle(d-1)^{n-1}$ $\displaystyle\geq(d-1)^{2}=(d-1)(d-1)$
$\displaystyle\geq(d-1)(3-1)=d+(d-2)$ $\displaystyle\geq d+(3-2)$
$\displaystyle\geq d.$

It follows that

$d^{n}\leq d^{n-1}(d-1)^{n-1}.$

Multiplying this inequality by the equation $1=d-(d-1)$, we have

$d^{n}\leq d^{n}(d-1)^{n-1}-d^{n-1}(d-1)^{n}.$

Adding the inequalities $0\leq(d-1)^{n}$ and $(d-1)^{n-1}\leq d^{n-1}$, we
obtain

$d^{n}+(d-1)^{n-1}\leq d^{n}(d-1)^{n-1}-d^{n-1}(d-1)^{n}+(d-1)^{n}+d^{n-1}.$

Rearranging,

$d^{n}-d^{n-1}+d^{n-1}(d-1)^{n}-(d-1)^{n}\leq d^{n}(d-1)^{n-1}-(d-1)^{n-1}.$

Finally, dividing both sides by $(d-1)^{n}$ yields the desired inequality.

######  Lemma 7.

The probability that more than a $\gamma$ fraction of the edges of
$\widetilde{H}$ are bad edges is at most $\varepsilon$.

This is our most difficult technical lemma, so we first give some intuition
behind the proof. Consider the special case where $m=2$, $\ell=1$ and $d=3$.
Observe that $d=2^{\ell}+1$, as in (4). Choose a random edge
$e^{*}=\\{u,v\\}\in E(\widetilde{H})$. For any positive integer $r$, let
$X_{r}$ be the random variable defined as the number of paths of length $r$
starting from $e^{*}$ in which the union of the subspaces of
$\mathbb{F}_{2}^{2}$ along $p$ do _not_ span $\mathbb{F}_{2}^{2}$. At $r=1$,
there are two such paths to consider: $(u,v)$ and $(v,u)$. Since $\ell=1$,
$Z(u,v)=Z(v,u)$ is a 1-dimensional subspace of $\mathbb{F}_{2}^{2}$, so both
of these paths fail to span the entire space. Thus, $X_{1}=2$ with probability
1. To compute $X_{2}$, observe that, since $d=3$, both of these “bad” paths of
length 1 can be extended in exactly 2 different ways to be paths of length 2.
So suppose the path $(u,v)$ can be extended to either $(u,v,w_{1})$ or
$(u,v,w_{2})$. If $Z(v,w_{1})\subseteq Z(u,v)$ (which happens with probability
$\frac{1}{3}<\frac{1}{2}$), then the extension $(u,v,w_{1})$ will still fail
to generate the space, so it will still be counted in $X_{2}$. Otherwise, with
probability more than $\frac{1}{2}$, the extension will generate the space,
and not be counted in $X_{2}$. The same holds for $(u,v,w_{2})$. Thus, as we
extend the bad path $(u,v)$ by 1 vertex, we have created 2 new potentially bad
paths, but each one immediately becomes a good path with probability
$>\frac{1}{2}$, so the expected number of bad extensions is less than 1.
Similarly, the expected number of bad extensions of $(v,u)$ is less than 1 as
well. More generally, this argument shows that the expected value of $X_{r}$
is strictly decreasing in $r$. Thus, with high probability, $X_{r}$ will
eventually hit zero, at which point we can conclude that $e^{*}$ is a good
edge.

This special case contains the main idea of the proof. Equation (4) is the
key, ensuring that the expected value of $X_{r}$ is decreasing: at each path
extension, $d-1=2^{\ell}$ new potentially bad paths are created, and each are
resolved with probability $>\frac{1}{2^{\ell}}$. The specific choice of $r$ in
(7) is just a bound on how large $r$ may need to be to ensure $X_{r}=0$ with
high probability.

######  Proof 5.3 (Proof of Lemma 7).

Let $e^{*}$ be a uniformly randomly chosen edge of $\widetilde{H}$. For each
$i\in[r]$, let $P_{i}$ be the set of paths of length $i$ from whose first two
vertices are the endpoints of $e^{*}$. For any path
$p=(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{n})$ in $\widetilde{H}$, we say that
the _dimension_ of $p$, denoted $\dim(p)$, is the dimension of the vector
space

$Z(p):=\text{span}\left(\bigcup_{i\in[n]}Z(v_{i-1},v_{i})\right).$

We define random variables ${X}_{1}{,}{X}_{2}{,}\dots,{X}_{r}$ as follows:

$X_{i}:=\sum_{p\in P_{i}}\left(d^{m-\dim(p)}-1\right).$

Note that, with probability 1,

$X_{1}=2(d^{m-\ell}-1),$ (8)

since there are only 2 paths of length 1 to consider (depending on which
direction $e^{*}$ is traversed), and each has dimension $\ell$. By definition,
$X_{i}\geq 0$ for all $i\in[r]$, and $e^{*}$ is a good edge if and only if
$X_{r}=0$. Thus, our goal is to upper-bound $\Pr[X_{r}\geq 1]$.

For any $2\leq i\leq r$ and $x\geq 1$,

$\mathbb{E}[X_{i}\ |\ X_{i-1}=x]\leq x-\frac{1}{2^{m\ell}}.$

######  Proof 5.4 (Proof of Claim.).

We prove that this holds even after additionally conditioning on any tuple of
realizations $R$ of the random subspaces along all paths in $P_{i-1}$ that is
consistent with $X_{i-1}=x$. Note that conditioning on these realizations also
fixes the value of $\dim(p_{0})$ for any $p_{0}\in P_{i-1}$.

We can split a path $p=(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{i})$ into two
subpaths $p_{0}:=(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{i-1})$ and
$p_{1}:=(v_{i-1},v_{i})$. When this happens, we say $p_{1}\succ p_{0}$ and
$p_{0}+p_{1}=p$. Using this decomposition, we obtain the following formula for
$X_{i}$:

$\displaystyle X_{i}$ $\displaystyle=\sum_{p_{0}\in P_{i-1}}\sum_{p_{1}\succ
p_{0}}(d^{m-\dim(p_{0}+p_{1})}-1)$ $\displaystyle=\sum_{p_{0}\in
P_{i-1}}\sum_{p_{1}\succ p_{0}}\begin{cases}d^{m-\dim(p_{0})}-1&\text{ if
}Z(p_{1})\subseteq Z(p_{0})\\\ d^{m-\dim(p_{0})-1}-1&\text{
otherwise}\end{cases}$

Note that the events that each of these $Z(p_{1})\subseteq Z(p_{0})$ are
independent, and also independent of $R$, since the girth of $\widetilde{H}$
is greater than $r$ and $i\leq r$. For convenience, let us denote

$f(p_{0},p_{1}):=\begin{cases}d^{m-\dim(p_{0})}-1&\text{ if }Z(p_{1})\subseteq
Z(p_{0})\\\ d^{m-\dim(p_{0})-1}-1&\text{ otherwise}\end{cases},$

so that

$X_{i}=\sum_{p_{0}\in P_{i-1}}\sum_{p_{1}\succ p_{0}}f(p_{0},p_{1}).$

Then

$\displaystyle\mathbb{E}[X_{i}\ |\ R]$ $\displaystyle=\sum_{p_{0}\in
P_{i-1}}\sum_{p_{1}\succ p_{0}}\mathbb{E}\left[f(p_{0},p_{1})\ |\ R\right]$
$\displaystyle=\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\mathbb{E}\left[f(p_{0},p_{1})\ |\ R\right]$ (since $f(p_{0},p_{1})=0$
for all $p_{0}$ of dimension $m$)
$\displaystyle=\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\left(\begin{array}[]{ll}\Pr[Z(p_{1})\subseteq Z(p_{0})\ |\
R](d^{n}-1)+\text{}\\\ (1-\Pr[Z(p_{1})\subseteq Z(p_{0})\ |\
R])(d^{n-1}-1)\end{array}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\Pr[Z(p_{1})\subseteq Z(p_{0})\ |\ R](d^{n}-d^{n-1})+d^{n-1}-1$
$\displaystyle\leq\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\left(\left(\frac{2^{\dim(p_{0})}-1}{2^{m}-1}\right)^{\ell}\left(d^{n}-d^{n-1}\right)+d^{n-1}-1\right).$

This inequality follows from the observation that, if we choose $\ell$
uniformly random vectors from $\mathbb{F}_{2}^{m}\setminus\\{0\\}$, each
vector lies within $Z(p_{0})$ with probability
$\frac{2^{\dim(p_{0})}-1}{2^{m}-1}$. We may think of choosing a random
$\ell$-dimensional subspace as repeatedly choosing independent uniformly
random nonzero vectors until we have $\ell$ independent vectors, so the
probability $Z(p_{1})\subseteq Z(p_{0})$ is at most the probability that just
the first $\ell$ vectors are contained in $Z(p_{0})$.

Note that, when $n:=m-\dim(p_{0})\geq 1$,

$\displaystyle\hskip
11.38092pt\left(\left(2^{\dim(p_{0})-m}\right)^{\ell}-\left(\frac{2^{\dim(p_{0})}-1}{2^{m}-1}\right)^{\ell}\right)\left(d^{n}-d^{n-1}\right)$
$\displaystyle=\left(\frac{(2^{\dim(p_{0})}(2^{m}-1))^{\ell}-((2^{\dim(p_{0})}-1)2^{m})^{\ell}}{(2^{m}(2^{m-1}))^{\ell}}\right)\left(d^{n}-d^{n-1}\right)$
$\displaystyle=\left(\frac{2^{m\ell}-2^{\dim(p_{0})\ell}}{(2^{m}(2^{m-1}))^{\ell}}\right)\left(d^{n}-d^{n-1}\right)$
$\displaystyle=\left(\frac{1-2^{\ell(\dim(p_{0})-m)}}{(2^{m-1})^{\ell}}\right)\left(d^{n}-d^{n-1}\right)$
$\displaystyle=\left(1-2^{-\ell
n}\right)\left(2^{m-1}\right)^{-\ell}\left(d^{n}-d^{n-1}\right)$
$\displaystyle\geq\left(1-2^{-\ell n}\right)\left(2^{m}-1\right)^{-\ell}$
$\displaystyle\geq\left(1-2^{-\ell}\right)2^{-m\ell}\ \ \ \ \ \text{(since
${n\geq 1}$)}$ $\displaystyle\geq 2^{-\ell}2^{-m\ell}\ \ \ \ \ \text{(since
${\ell\geq 1}$)}$ $\displaystyle=\frac{1}{2^{(m+1)\ell}}.$

Therefore,

$\displaystyle\left(\frac{2^{\dim(p_{0})}-1}{2^{m}-1}\right)^{\ell}\left(d^{n}-d^{n-1}\right)+d^{n-1}-1$
$\displaystyle\leq\left(2^{\dim(p_{0})-m}\right)^{\ell}\left(d^{n}-d^{n-1}\right)+d^{n-1}-1-\frac{1}{2^{(m+1)\ell}}$
$\displaystyle=\left(\frac{1}{(2^{\ell})^{n}}\right)\left(d^{n}-d^{n-1}\right)+d^{n-1}-1-\frac{1}{2^{(m+1)\ell}}$
$\displaystyle=\left(\frac{d^{n}-d^{n-1}}{(d-1)^{n}}+d^{n-1}-1\right)-\frac{1}{2^{(m+1)\ell}}$
(from the definition of $d$ in (4))
$\displaystyle\leq\frac{d^{n}-1}{d-1}-\frac{1}{2^{(m+1)\ell}}\ \ \ \ \
\text{(from Lemma \ref{lemWierdIntegerBound})}.$

Putting this all together, we have

$\displaystyle\mathbb{E}[X_{i}\ |\ R]$
$\displaystyle\leq\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\left(\left(\frac{2^{\dim(p_{0})}-1}{2^{m}-1}\right)^{\ell}\left(d^{n}-d^{n-1}\right)+d^{n-1}-1\right)$
$\displaystyle\leq\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\sum_{p_{1}\succ
p_{0}}\left(\frac{d^{n}-1}{d-1}-\frac{1}{2^{(m+1)\ell}}\right)$
$\displaystyle\leq\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq
1\end{subarray}}\left(d^{n}-1-\frac{d-1}{2^{(m+1)\ell}}\right)$
$\displaystyle=\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}\left(d^{n}-1-\frac{1}{2^{m\ell}}\right)\
\ \ \ \ \text{(from (\ref{equChooseD}))}$
$\displaystyle\leq\left(\sum_{\begin{subarray}{c}p_{0}\in P_{i-1}\\\
n:=m-\dim(p_{0})\geq 1\end{subarray}}d^{n}-1\right)-\frac{1}{2^{m\ell}}$
$\displaystyle=\left(\sum_{p_{0}\in
P_{i-1}}\left(d^{m-\dim(p_{0})}-1\right)\right)-\frac{1}{2^{m\ell}}$ (since
$n=0$ terms contribute zero to the sum) $\displaystyle=x-\frac{1}{2^{m\ell}},$

where in the final inequality we have used the assumption that $R$ is
consistent with $X_{i-1}=1$, so there is at least one term in the sum, i.e.,
at least one bad path. Thus, Claim 5.3 holds.

Returning to the proof of Lemma 7, we now suppose toward a contradiction that
$\Pr[X_{r}\geq 1]>\gamma\varepsilon$. Since $X_{i}=0$ implies that $X_{j}=0$
for all $i\leq j$, it follows that, for all $i\in\\{1,2,3,\dots,r-1\\}$,

$\Pr[X_{i}\geq 1]>\gamma\varepsilon.$ (9)

For $2\leq i\leq r$, observe that

$\displaystyle\mathbb{E}[X_{i}]$ $\displaystyle=\sum_{x\geq
0}\Pr[X_{i-1}=x]\mathbb{E}[X_{i}\ |\ X_{i-1}=x]$
$\displaystyle=\Pr[X_{i-1}=0]\mathbb{E}[X_{i}\ |\ X_{i-1}=0]+\sum_{x\geq
1}\Pr[X_{i-1}=x]\mathbb{E}[X_{i}\ |\ X_{i-1}=x]$ $\displaystyle\leq
0+\sum_{x\geq 1}\Pr[X_{i-1}=x]\left(x-\frac{1}{2^{m\ell}}\right)\ \ \ \ \
\text{(by Claim \ref{claExpectationDecreasing})}$
$\displaystyle=\mathbb{E}[X_{i-1}]-\frac{\Pr[X_{i-1}\geq 1]}{2^{m\ell}}.$

Iteratively applying this inequality for $i=r,r-1,\dots,3,2$, we conclude that

$\displaystyle\mathbb{E}[X_{r}]$
$\displaystyle=\mathbb{E}[X_{1}]-\sum_{i=1}^{r-1}\frac{\Pr[X_{i}\geq
1]}{2^{m\ell}}$
$\displaystyle<2(d^{m-\ell}-1)-\sum_{i=1}^{r-1}\frac{\gamma\varepsilon}{2^{m\ell}}\
\ \ \ \ \text{(from (\ref{equX1Equals}) and (\ref{equAllXProbablyNonzero}))}$
$\displaystyle=2(d^{m-\ell}-1)-\frac{(r-1)\gamma\varepsilon}{2^{m\ell}}$
$\displaystyle\leq 0\ \ \ \ \ \text{(from the definition of $r$ in
(\ref{equChooseR}))},$

which is a contradiction, since $X_{r}$ can never be negative.

Hence,

$\Pr[e^{*}\text{ is a bad edge}]=\Pr[X_{r}\geq 1]\leq\gamma\varepsilon,$

so the expected fraction of bad edges is at most $\gamma\varepsilon$. By
Markov’s inequality, the probability that the fraction of bad edges is greater
than $\gamma$ is thus at most $\varepsilon$.

######  Lemma 8.

With probability at least $1-\varepsilon$, the satisfiability of
$\widetilde{U}_{2}$ is less than

$\left(1-\gamma\right)\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta\right).$

######  Proof 5.5.

Call a subgraph of $\widetilde{H}$ _large_ if it contains all of the vertices
of $\widetilde{H}$ and at least a $(\frac{2}{d}+\delta)$ fraction of the edges
of $\widetilde{H}$. If any assignment satisfies at least a

$\left(1-\gamma\right)\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta\right)=\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\frac{\delta}{2^{\ell}}\right)$

fraction of the constraints in $\widetilde{U}_{2}$, then, since at most one
constraint from each bundle can be satisfied, and there are $2^{\ell}$
constraints in each bundle, the assignment must satisfy the bundles of at
least a

$2^{\ell}\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\frac{\delta}{2^{\ell}}\right)=\frac{1}{2^{\ell-1}+\frac{1}{2}}+\delta=\frac{2}{d}+\delta$

fraction of edges. (Recall that to “satisfy a bundle” is to satisfy one
constraint in the bundle.) In other words, any satisfying assignment must
completely satisfy all bundles on some large subgraph. Therefore, by the union
bound, the probability that some assignment satisfies at least a
$\left(1-\gamma\right)\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta\right)$
fraction of constraints is at most the number of large subgraphs times the
probability that some assignment satisfies all bundles on a given large
subgraph. Supposing that $\widetilde{H}$ has $n$ vertices, the number of large
subgraphs of $\widetilde{H}$ is bounded by $2^{\frac{nd}{2}}$, the total
number of subgraphs containing all vertices of $\widetilde{H}$. To bound the
probability that some assignment satisfies all bundles on a large subgraph, we
first note that the probability of an arbitrary assignment satisfying all
bundles is at most

$\left(\frac{2^{\ell}}{2^{m}}\right)^{\frac{nd}{2}\left(\frac{2}{d}+\delta\right)}=2^{\wedge}\left[(\ell-m)\frac{nd}{2}\left(\frac{2}{d}+\delta\right)\right],$

since there are at least $\frac{nd}{2}\left(\frac{2}{d}+\delta\right)$ edges
in any large subgraph, and each bundle is satisfied independently with
probability $\frac{2^{\ell}}{2^{m}}$. Thus, applying the union bound again,
the probability that some assignment satisfies all bundles on a given large
subgraph is at most $(2^{m})^{n}$ times this quantity. So, in total, the
probability that some assignment satisfies at least a
$\left(1-\gamma\right)\left(\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta\right)$
fraction of constraints is at most

$\displaystyle
2^{\wedge}\left[\frac{nd}{2}+mn+(\ell-m)\frac{nd}{2}\left(\frac{2}{d}+\delta\right)\right]$
$\displaystyle=$ $\displaystyle
2^{\wedge}\left[n\left(\frac{d}{2}+\frac{\delta d}{2}\left(\frac{2}{\delta
d}+1\right)\ell-\frac{\delta d}{2}\cdot m\right)\right]$ $\displaystyle\leq$
$\displaystyle 2^{\wedge}\left[n\hskip 1.60004pt\left(\frac{d}{2}+\frac{\delta
d}{2}\left(\frac{2}{\delta d}+1\right)\ell-\frac{\delta
d}{2}\cdot\left(\frac{1}{\delta}+\left(\frac{2}{\delta
d}+1\right)\ell-\frac{2}{\delta d}\log_{2}(\varepsilon)\right)\right)\right]\
\ \ \ \ \text{(from (\ref{equChooseM}))}$ $\displaystyle=$ $\displaystyle
2^{n\log_{2}(\varepsilon)}$ $\displaystyle\leq$ $\displaystyle
2^{\log_{2}(\varepsilon)}\ \ \ \ \ \text{(because
${\varepsilon<1\implies\log_{2}(\varepsilon)<0,\text{ and }n>0}$)}$
$\displaystyle=$ $\displaystyle\varepsilon.$

Therefore, the probability that no assignment satisfies at least this fraction
of constraints is at least $1-\varepsilon$.

######  Lemma 9.

With probability at least $1-2\varepsilon$, the satisfiability of $U_{2}$ (and
thus of $\mathcal{G}(U_{2})$) is less than

$\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta.$

######  Proof 5.6.

By Lemma 7, the probability that less than a $(1-\gamma)$ fraction of edges of
$\widetilde{H}$ are good edges is at most $\varepsilon$. By Lemma 8, the
probability that $\widetilde{U}_{2}$ is
$(1-\gamma)\left(\frac{\alpha}{2^{\ell}}\right)$-satisfiable is at most
$\varepsilon$ as well. By the union bound, the probability that either of
these two events occurs is at most $2\varepsilon$, so the probability that
neither event occurs is at least $1-2\varepsilon$. So it suffices to prove
that, whenever at least a $(1-\gamma)$ fraction of the edges of
$\widetilde{H}$ are good edges, if $\widetilde{U}_{2}$ is not
$(1-\gamma)\left(\frac{\alpha}{2^{\ell}}\right)$-satisfiable, then $U_{2}$ is
not $\left(\frac{\alpha}{2^{\ell}}\right)$-satisfiable.

We instead prove the contrapositive, that if at least a
$\left(\frac{\alpha}{2^{\ell}}\right)$ fraction of constraints are satisfiable
in $U_{2}$, then at least a $(1-\gamma)\left(\frac{\alpha}{2^{\ell}}\right)$
fraction of constraints are satisfiable in $\widetilde{U}_{2}$. Suppose that
$\widetilde{U}_{2}$ has a total of $c$ constraints. Then $U_{2}$ has at least
$(1-\gamma)c$ constraints. So if at least a
$\left(\frac{\alpha}{2^{\ell}}\right)$ fraction of constraints are satisfiable
in $U_{2}$, it means that at least
$\left(\frac{\alpha}{2^{\ell}}\right)(1-\gamma)c$ constraints of $U_{2}$ are
satisfied by some assignment $x_{v}$. Since $U_{2}$ and $\widetilde{U}_{2}$
have the same variable set, and all of the constraints of $U_{2}$ are also
constraints of $\widetilde{U}_{2}$, it follows that $x_{v}$ must satisfy
$\left(\frac{\alpha}{2^{\ell}}\right)(1-\gamma)c$ constraints of
$\widetilde{U}_{2}$ as well, that is, at least a
$\left(\frac{\alpha}{2^{\ell}}\right)(1-\gamma)$ fraction of constraints.

###  5.3. Proof of $C^{k}$-equivalence

The following Lemma is a generalization of Duplicator’s strategy for
determining $g^{*}(v_{4})$ in the example from Section 4.3.

######  Lemma 10.

Let $p=(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{n})$ be a path in $H$ of length
$n\geq r$. Given any values in $\mathbb{F}_{2}^{m}$ for $g^{*}(v_{0})$ and
$g^{*}(v_{n})$, it is possible to extend $g^{*}$ to all of the intermediate
vertices of $p$ so that the map $f(x_{v}^{g}):=x_{v}^{g+g^{*}(v)}$ is a
partial isomorphism between $\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$ over
the set $\\{x_{v}^{g}\ |\ v\in p,\ g\in\mathbb{F}_{2}^{m}\\}$.

######  Proof 5.7.

Since $H$ contains only good edges and $p$ has length at least $r$, there
exists a set of vectors

$B\subseteq\bigcup_{i\in[n]}Z(v_{i-1},v_{i})$

forming a basis of $\mathbb{F}_{2}^{m}$. Write $h(i)$ for the number of basis
vectors in $Z(v_{i-1},v_{i})$, and denote these vectors by

$B=\bigcup_{i\in[n]}\\{z_{i,j}\ |\ j\in[h(i)]\\},$

where each $z_{i,j}\in Z(v_{i-1},v_{i})$. Since $B$ is a basis, there exist
coefficients $c_{i,j}$ such that

$g^{*}(v_{0})-g^{*}(v_{n})-\sum_{i\in[n]}b(v_{i-1},v_{i})=\sum_{i\in[n]}\sum_{j\in[h(i)]}c_{i,j}z_{i,j}.$
(10)

For each $i$ in order from $1$ to $n$, inductively define

$g^{*}(v_{i}):=g^{*}(v_{i-1})-\sum_{j\in[h(i)]}c_{i,j}z_{i,j}-b(v_{i-1},v_{i}).$

Note that, by expanding the inductive definition for $g^{*}(v_{n})$, we have

$\displaystyle g^{*}(v_{n})$
$\displaystyle=g^{*}(v_{n-1})-\sum_{j\in[h(n)]}c_{n,j}z_{n,j}-b(v_{n-1},v_{n})$
$\displaystyle=g^{*}(v_{n-2})-\sum_{j\in[h(n-1)]}c_{n-1,j}z_{n-1,j}-b(v_{n-2},v_{n-1})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \hskip
18.20973pt-\sum_{j\in[h(n)]}c_{n,j}z_{n,j}-b(v_{n-1},v_{n})$
$\displaystyle=g^{*}(v_{n-3})-\sum_{j\in[h(n-2)]}c_{n-2,j}z_{n-2,j}-b(v_{n-3},v_{n-2})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \hskip
18.20973pt-\sum_{j\in[h(n-1)]}c_{n-1,j}z_{n-1,j}-b(v_{n-2},v_{n-1})$
$\displaystyle\ \ \ \ \ \ \ \ \ \ \hskip
18.20973pt-\sum_{j\in[h(n)]}c_{n,j}z_{n,j}-b(v_{n-1},v_{n})$
$\displaystyle=\dots$
$\displaystyle=g^{*}(v_{0})-\sum_{i\in[n]}\left(b(v_{i-1},v_{i})+\sum_{j\in[h(i)]}c_{i,j}z_{i,j}\right),$

so our inductive definition agrees with the given value of $g^{*}(v_{n})$ by
(10). Finally, observe that, for any $i\in[n]$ and any arbitrary
$g_{i-1},g_{i},z\in\mathbb{F}_{2}^{m}$,

$\displaystyle x_{v_{i}}^{g_{i}}-x_{v_{i-1}}^{g_{i-1}}=z$ $\displaystyle\text{
is an equation in }\mathcal{G}(U_{1})$ $\displaystyle\iff$
$\displaystyle(x_{v_{i}}^{g_{i}}+g_{i})-(x_{v_{i-1}}^{g_{i-1}}+g_{i-1})=z$
$\displaystyle\text{ is an equation in }U_{1}$ $\displaystyle\iff$
$\displaystyle(x_{v_{i}}^{g_{i}}+g_{i}+g^{*}(v_{i-1}))-(x_{v_{i-1}}^{g_{i-1}}+g_{i-1}+g^{*}(v_{i-1}))=z$
$\displaystyle\text{ is an equation in }U_{1}$ $\displaystyle\iff$
$\displaystyle(x_{v_{i}}^{g_{i}}+g_{i}+g^{*}(v_{i-1}))-(x_{v_{i-1}}^{g_{i-1}}+g_{i-1}+g^{*}(v_{i-1}))=z+\sum_{j\in[h(i)]}c_{i,j}z_{i,j}$
$\displaystyle\text{ is an equation in }U_{1}$ (since
${\sum_{j\in[h(i)]}c_{i,j}z_{i,j}\in Z(v_{i-1},v_{i})}$) $\displaystyle\iff$
$\displaystyle(x_{v_{i}}^{g_{i}}+g_{i}+g^{*}(v_{i-1}))-(x_{v_{i-1}}^{g_{i-1}}+g_{i-1}+g^{*}(v_{i-1}))=z+\sum_{j\in[h(i)]}c_{i,j}z_{i,j}+b(v_{i-1},v_{i})$
$\displaystyle\text{ is an equation in }U_{2}$ $\displaystyle\iff$
$\displaystyle(x_{v_{i}}+g_{i}+g^{*}(v_{i-1})-\sum_{j\in[h(i)]}c_{i,j}z_{i,j}-b(v_{i-1},v_{i}))-(x_{v_{i-1}}+g_{i-1}+g^{*}(v_{i-1}))=z$
$\displaystyle\text{ is an equation in }U_{2}$ $\displaystyle\iff$
$\displaystyle
x_{v_{i}}^{g_{i}+g^{*}(v_{i-1})-\sum_{j\in[h(i)]}c_{i,j}z_{i,j}-b(v_{i-1},v_{i})}-x_{v_{i-1}}^{g_{i-1}+g^{*}(v_{i-1})}=z$
$\displaystyle\text{ is an equation in }\mathcal{G}(U_{2})$
$\displaystyle\iff$ $\displaystyle
x_{v_{i}}^{g_{i}+g^{*}(v_{i})}-x_{v_{i-1}}^{g_{i-1}+g^{*}(v_{i-1})}=z$
$\displaystyle\text{ is an equation in }\mathcal{G}(U_{2})$
$\displaystyle\iff$ $\displaystyle
f(x_{v_{i}}^{g_{i}})-f(x_{v_{i-1}}^{g_{i-1}})=z$ $\displaystyle\text{ is an
equation in }\mathcal{G}(U_{2}),$

so $f$ is a partial isomorphism over the entire path.

We are now ready to prove $C^{k}$-equivalence. Duplicator’s strategy is to
maintain consistency between $\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$
over a minimal tree in $H$ spanning all _pebbled vertices_ (that is, vertices
$v\in V(H)$ such that some variable $x_{v}^{g}$ is pebbled in one of the two
structures). Since $H$ has high girth relative to $r$, Spoiler will never be
able to expose a cycle of inconsistency, as Duplicator will be able to apply
Lemma 10 at some point during the cycle.

######  Lemma 11.

$\mathcal{G}(U_{1})\equiv_{C^{k}}\mathcal{G}(U_{2})$.

######  Proof 5.8.

It is without loss of generality to assume $H$ is connected, for otherwise
Duplicator can apply the strategy presented here on each connected component
separately. On every round $i$ of the $k$-pebble bijective game played on
$\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$, for any $u\in V(H)$, let
$T_{i}(u)$ be a minimal tree containing $u$ and all pebbled vertices just
after Spoiler has picked up a pebble. Let $P_{i}(u)$ denote the set of all of
the vertices in $T_{i}(u)$ which have degree at least 3 or contain a pebbled
vertex, also including $u$. Define $T_{i}:=T_{i}(u^{*}_{i})$ and
$P_{i}:=P_{i}(u^{*}_{i})$, where $u^{*}_{i}$ is the new vertex pebbled in
round $i$. Finally, define the forest $F_{i}(u)$ to be the subgraph of
$T_{i}(u)\setminus T_{i-1}$ (what this notation means is, remove all edges in
$T_{i-1}$ from $T_{i}(u)$, then remove isolated vertices) consisting of all
segments in $T_{i}(u)$ between vertices in $P_{i}(u)\cup V(T_{i-1})$ which
have length less than $r$. See Figure 4 for an example.

Figure 4. The tree consisting of all vertices and edges in the figure is
$T_{i}(u)$. This is a minimal tree that includes all pebbled vertices, which
are filled in red, and vertex $u$, which is near the top left corner. The
green dashed line outlines the boundary of $T_{i-1}$ (not all vertices and
edges of this tree are shown, just those that intersect $T_{i}(u)$). Assuming
that $r=3$ (which is, of course, not nearly large enough; this is just for the
purpose of illustration), the forest $F_{i}(u)$ is as depicted in blue,
consisting of the lettered vertices $A$ through $H$ and all of the edges
between those vertices.

On any round $i$, for any vertex $u\in V(H)$, any path in $T_{i}(u)$ passes
through at most $k$ vertices in $P_{i}(u)$.

######  Proof 5.9 (Proof of Claim).

Let $p=(v_{0},{v}_{1}{,}{v}_{2}{,}\dots,{v}_{n})$ be a path in $T_{i}(u)$.
Consider the following map $h:p\cap P_{i}(u)\to V(T_{i}(u))$:

$h(v_{i}):=\begin{cases}v_{i}&\text{if }\deg(v_{i})<3\\\ \text{a pebbled
vertex (or $u$) reachable}&\\\ \text{from $v_{i}$ in
$T_{i}(u)\setminus\\{v_{i-1},v_{i+1}\\}$}&\text{if }\deg(v_{i})\geq
3\end{cases}$

Note that such a vertex in the second case above always exists when $v_{i}$
has degree at least 3, and is necessarily different from all other vertices in
the image of $h$. Thus, $h$ is injective. Also, since vertices in $P_{i}(u)$
of degree less than 3 must be pebbled (or $u$), the output of $h(v_{i})$ must
always be a pebbled vertex (or $u$). Thus, we have an injection from $p\cap
P_{i}(u)$ to a set of pebbled vertices (plus $u$), of which there are at most
$k$ (since one pebble pair has been picked up), so $\left|{p\cap
P_{i}(u)}\right|\leq k$.

On any round $i$, for any vertex $u\in V(H)$, there does not exist any path
contained in $F_{i}(u)$ with both endpoints in $T_{i-1}$.

######  Proof 5.10 (Proof of Claim).

Suppose toward a contradiction that there was such a path $p_{1}$, joining
$v_{1},v_{3}\in T_{i-1}$. Let $v_{2}$ be the first vertex in $p_{1}$ that is
contained within $T_{i-1}$, excluding $v_{1}$ (it could just be $v_{3}$ if
there are no earlier places where $p$ crosses $T_{i-1}$). Since $T_{i-1}$ is
connected, there must be some path $p_{2}$ joining $v_{1}$ and $v_{2}$ in
$T_{i-1}$. Since $p_{1}$ is contained in $F_{i}(u)$, which shares no edges
with $T_{i-1}$, $p_{1}$ and $p_{2}$ share no edges. Aside from $v_{1}$ and
$v_{2}$, they do not share any common vertices either, from the way that
$v_{2}$ was chosen. So together, $p_{1}$ and $p_{2}$ form a cycle. Since
$p_{1}$ is contained within $T_{i}(u)$, by Claim 5.8 it intersects at most $k$
vertices in $P_{i}(u)$. Since, additionally, $p_{1}$ is contained in
$F_{i}(u)$, the length of each of the $\leq(k+1)$ segments between vertices in
$P_{i}(u)$ and the endpoints is strictly less than $r$. Thus, $p_{1}$ has
length strictly less than $(k+1)r$. Since $p_{2}$ is contained within
$T_{i-1}$, which is minimal, $p_{2}$ cannot contain any subpaths of length
$(k+1)r$ which do not intersect $P_{i-1}$, for otherwise, swapping out such a
subpath for $p_{1}$ would yield a strictly smaller tree. Applying Lemma 5.8 to
round $i-1$ and vertex $u^{*}_{i-1}$, we have that at most $k$ vertices of
$p_{2}$ intersect $P_{i-1}$, so $p_{2}$ has length at most $k(k+1)r$. Thus,
concatenating $p_{1}$ and $p_{2}$ yields a cycle of size strictly less than

$(k+1)r+k(k+1)r=(k+1)^{2}r$

in $H$. This contradicts the fact that $H$ was constructed to have girth at
least $(k+1)^{2}r$. Hence, no such path $p_{1}$ can exist.

Returning to the proof of $C^{k}$-equivalence, let $X_{i}(u)$ denote the
variable set of $\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$ restricted to
$T_{i}(u)$,

$X_{i}(u):=\\{x_{v}^{g}\ |\ v\in T_{i}(u),\ g\in\mathbb{F}_{2}^{m}\\}.$

On each round $i$, Duplicator’s strategy is to define functions

$g^{*}(i,u,\cdot):V(T_{i}(u))\to\mathbb{F}_{2}^{m}$

for each $u\in V(H)$, satisfying the following two properties:

  1. (1)

For any pebbled vertex $v\in V(H)$,

$g^{*}(i,u,v)=g^{*}(i-1,u^{*}_{i-1},v).$

  2. (2)

The map $f_{i,u}:X_{i}(u)\to X_{i}(u)$ defined by

$f_{i,u}(x_{v}^{g}):=x_{v}^{g+g^{*}(i,u,v)}$

gives a partial isomorphism between $\mathcal{G}(U_{1})$ and
$\mathcal{G}(U_{2})$.

Duplicator then presents Spoiler with the bijection

$f_{i}(x_{v}^{g}):=x_{v}^{g+g^{*}(i,v,v)},$

which respects existing pebble pairs by property (1). No matter which vertex
$u^{*}_{i}$ Spoiler chooses, the map $f_{i,u^{*}_{i}}$ agrees with $f_{i}$
over $u^{*}_{i}$, so we know that $f_{i,u^{*}_{i}}$ respects all pebble pairs
since $f_{i}$ does. Therefore, since the edge between any pair of adjacent
pebbled vertices of $H$ must be in $T_{i}$ (by applying Claim 5.8 to round
$i+1$), Spoiler cannot win, as the map sending each pebbled element in the
universe of $\mathcal{G}(U_{1})$ to the correspondingly-pebbled element of
$\mathcal{G}(U_{2})$ is a restriction of $f_{i,u^{*}_{i}}$, which is a partial
isomorphism by property (2).

All that remains is to show how Duplicator can satisfy properties (1) and (2)
on each round $i$, assuming inductively that they are satisfied on round
$i-1$. Fix a vertex $u\in V(G)$. Duplicator defines $g^{*}(i,u,\cdot)$ in
three steps: first over $V(T_{i}(u))\cap V(T_{i-1})$, then over
$V(F_{i}(u))\setminus V(T_{i-1})$, then finally, over the remaining vertices
$(V(T_{i}(u))\setminus V(T_{i-1}))\setminus V(F_{i}(u))$.

Over $V(T_{i}(u))\cap V(T_{i-1})$, Duplicator simply sets

$g^{*}(i,u,v):=g^{*}(i-1,u^{*}_{i-1},v),$

which is well-defined over $V(T_{i-1})$ and clearly satisfies both properties
(1) and (2), inductively assuming that $g^{*}(i-1,u^{*}_{i-1},\cdot)$ did.
Since $V(T_{i}(u))\cap V(T_{i-1})$ contains all pebbled vertices, we no longer
have to worry about property (1); we just have to define $g^{*}(i,u,\cdot)$ on
the remainder of $V(T_{i}(u))$ so that property (2) is satisfied.

Duplicator then uses the following algorithm to define $g^{*}(i,u,\cdot)$ over
$V(F_{i}(u))\setminus V(T_{i-1})$:

1 while  _true_ do

2 if  _there exists $\\{v_{1},v_{2}\\}\in E(F_{i}(u))$ such that
$g^{*}(i,u,v_{1})$ is defined but $g^{*}(i,u,v_{2})$ is not defined_ then

3 $g^{*}(i,u,v_{2})\leftarrow g^{*}(i,u,v_{1})+b(v_{1},v_{2})$;

4

5 else if  _there exists $v\in V(F_{i}(u))$ such that $g^{*}(i,u,v)$ is not
defined_ then

6 $g^{*}(i,u,v)\leftarrow$ anything;

7

8 else

9 return __;

10

11 end if

12

13 end while

Observe that the constraints involving each edge in $F_{i}(u)$ considered in
the first case are preserved by $f_{i,u}$: for all
$g_{1},g_{2},z\in\mathbb{F}_{2}^{m}$,

$\displaystyle x_{v_{1}}^{g_{1}}-x_{v_{2}}^{g_{2}}=z$ $\displaystyle\text{ is
an equation in }\mathcal{G}(U_{1})$ $\displaystyle\iff$
$\displaystyle(x_{v_{1}}+g_{1})-(x_{v_{2}}+g_{2})=z$ $\displaystyle\text{ is
an equation in }U_{1}$ $\displaystyle\iff$
$\displaystyle(x_{v_{1}}+g_{1})-(x_{v_{2}}+g_{2})=z+b(v_{1},v_{2})$
$\displaystyle\text{ is an equation in }U_{2}$ $\displaystyle\iff$
$\displaystyle(x_{v_{1}}+g_{1}+g^{*}(i,u,v_{1}))-(x_{v_{2}}+g_{2}+g^{*}(i,u,v_{1})+b(v_{1},v_{2}))=z$
$\displaystyle\text{ is an equation in }U_{2}$ $\displaystyle\iff$
$\displaystyle
x_{v_{1}}^{g_{1}+g^{*}(i,u,v_{1})}-x_{v_{2}}^{g_{2}+g^{*}(i,u,v_{1})+b(v_{1},v_{2})}=z$
$\displaystyle\text{ is an equation in }\mathcal{G}(U_{2})$
$\displaystyle\iff$ $\displaystyle
x_{v_{1}}^{g_{1}+g^{*}(i,u,v_{1})}-x_{v_{2}}^{g_{2}+g^{*}(i,u,v_{2})}=z$
$\displaystyle\text{ is an equation in }\mathcal{G}(U_{2})$
$\displaystyle\iff$ $\displaystyle
f_{i,u}(x_{v_{1}}^{g_{1}})-f_{i,u}(x_{v_{2}}^{g_{2}})=z$ $\displaystyle\text{
is an equation in }\mathcal{G}(U_{2}).$

For example, if $F_{i}(u)$ is as in Figure 4, then the first iteration of the
algorithm would define $g^{*}(i,u,B)$ so that the constraints involving $A$
and $B$ are consistent under $f_{i,u}$. The next iteration would then define
$g^{*}(i,u,C)$ so that the constraints involving $B$ and $C$ are consistent.
Similarly, the next two iterations would set $g^{*}(i,u,D)$ and $g^{*}(i,u,E)$
(these could happen in either order). On the fifth iteration, we would hit the
second case of the algorithm and set one of $g^{*}(i,u,F)$, $g^{*}(i,u,G)$ or
$g^{*}(i,u,H)$ arbitrarily. The final two iterations would set the other two
values according to the first case.

Since the edges encountered in the first case are always made consistent, the
only way that $f_{i,u}$ could fail to be a partial isomorphism over $F_{i}(u)$
is if, at some iteration, there were two different edges satisfying the
condition in the first case that yielded different values for
$g^{*}(i,u,v_{2})$ for some $v_{2}$. Since $F_{i}(u)$ is a forest, the only
way that this could happen is if some connected component of $F_{i}(u)$ had
two distinct vertices $v_{1}$ and $v_{2}$ on which $g^{*}(i,u,\cdot)$ was
already defined before the algorithm started, which can only happen if
$v_{1},v_{2}\in V(T_{i-1})$. But this means that there is a path in $F_{i}(u)$
from $v_{1}$ to $v_{2}$ that violates Claim 5.8. Thus, property (2) is still
satisfied.

At this point, the only remaining edges of $T_{i}(u)$ which Duplicator needs
to worry about are those which are in $T_{i}(u)\setminus T_{i-1}$ but are not
in $F_{i}(u)$. By the definition of $F_{i}(u)$, this consists of paths of
length at least $r$, each with a disjoint set of intermediate vertices. Since
$g^{*}(i,u,\cdot)$ has not yet been defined on any of the intermediate
vertices, Duplicator can apply Lemma 10 to each one separately. Thus, property
(2) is satisfied over the entirety of $X_{i}(u)$.

We have shown that Duplicator has a winning strategy in the $k$-pebble
bijective game played on $\mathcal{G}(U_{1})$ and $\mathcal{G}(U_{2})$, so, by
Theorem 2.2, $\mathcal{G}(U_{1})\equiv_{C^{k}}\mathcal{G}(U_{2})$.

###  5.4. Proof of main result

######  Theorem 12.

For any $\delta>0$ and any positive integer $\ell$, there exists a positive
integer $q$ such that no sentence of FPC distinguishes UG($q$) instances
(encoded as $\tau_{\textup{{UG}}(q)}$-structures) of optimal value
$\geq\frac{1}{2^{\ell}}$ from those of optimal value
$<\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta$.

######  Proof 5.11.

Let $\delta$ and $\ell$ be given, pick an arbitrary
$\varepsilon\in(0,\frac{1}{2})$, then let $q$ be as defined in Section 5.1.
Suppose toward a contradiction that there was an FPC sentence $\phi$
distinguishing the two cases. Then $\phi$ can be translated into a logically
equivalent sentence $\phi^{\prime}$ of $C^{k}$ for some fixed $k$. Given this
value of $k$, let $\mathbb{A}_{k}:=\mathcal{G}(U_{1})$ and
$\mathbb{B}_{k}:=\mathcal{G}(U_{2})$ be as defined in Section 5.1. By Lemmas
5, 9 and 11, with probability at least $1-2\varepsilon$, we will have that

$\displaystyle\textup{opt}(\mathbb{A}_{k})\geq\frac{1}{2^{\ell}},$
$\displaystyle\textup{opt}(\mathbb{B}_{k})<\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta,$

yet $\mathbb{A}_{k}\equiv_{C^{k}}\mathbb{B}_{k}$. Since $1-2\varepsilon>0$,
this implies that there is _some_ pair of $\tau_{\textup{{UG}}(q)}$-structures
$(\mathbb{A}_{k},\mathbb{B}_{k})$ produced by this construction satisfying
these properties. This is a contradiction, since $\phi^{\prime}$ cannot
distinguish $\mathbb{A}_{k}$ and $\mathbb{B}_{k}$ as they are
$C^{k}$-equivalent, so $\phi$ cannot distinguish them either.

######  Corollary 13.

For any $\alpha\in(0,1]$, for sufficiently large $q$ there does not exist an
FPC-definable $\alpha$-approximation algorithm for UG$(q)$.

######  Proof 5.12.

Let $\alpha\in(0,1]$ be given. Define

$\displaystyle\ell:=\left\lceil\frac{2-\log_{2}(\alpha)}{2}\right\rceil,$
$\displaystyle\delta:=\frac{1}{2^{2\ell-1}+2^{\ell-1}}.$

Note that $\ell$ is a positive integer and $\delta>0$. Let

$\displaystyle c$ $\displaystyle:=\frac{1}{2^{\ell}},$ $\displaystyle s$
$\displaystyle:=\frac{1}{2^{2\ell-1}+2^{\ell-1}}+\delta=\frac{2}{2^{2\ell-1}+2^{\ell-1}}$

Then, by Theorem 12, there exists a positive integer $q$ such that no sentence
of FPC distinguishes $\tau_{\textup{{UG}}(q)}$-structures with optimal value
$\geq c$ from those with optimal value $<s$. Observe that

$\displaystyle\frac{s}{c}$
$\displaystyle=\frac{\frac{2}{2^{2\ell-1}+2^{\ell-1}}}{\frac{1}{2^{\ell}}}$
$\displaystyle=\frac{2^{\ell+1}}{2^{2\ell-1}+2^{\ell-1}}$
$\displaystyle\leq\frac{2^{\ell+1}}{2^{2\ell-1}}$ $\displaystyle=2^{2-2\ell}$
$\displaystyle\leq 2^{2-2\left(\frac{2-\log_{2}(\alpha)}{2}\right)}\ \ \ \ \
\text{(since ${\ell\geq\frac{2-\log_{2}(\alpha)}{2}}$)}$
$\displaystyle=\alpha.$

Therefore, it follows from Lemma 2 that there is no FPC-definable
$\alpha$-approximation algorithm for UG($q$).

##  6\. Conclusion

This paper has two objectives. The first is to introduce a new proof idea into
the arsenal of tools for CFI-constructions. Our main challenge was that, to
prove an FPC-inapproximability result, it is not sufficient to have Duplicator
maintain the standard kind of invariant used in CFI-constructions: that the
two structures are always isomorphic by a bijection agreeing with all pebble
pairs, except at one place where the isomorphism breaks down. Using techniques
from graph theory and linear algebra, we have shown how Duplicator can win the
$k$-pebble bijective game while only maintaining an extremely weak
invariant—consistency over a very small portion of the two structures.
Hopefully this approach can be extended to other approximation settings as
well.

The second objective is to make progress on the FPC-version of the Unique
Games Conjecture. We have established an FPC-inapproximability gap which is
competitive with recent results in ordinary complexity theory about
polynomial-time approximation algorithms, yet our result holds without the
assumption that $\mathsf{P}\neq\mathsf{NP}$. Of course, our proof method is
entirely different than the proof methods used in ordinary complexity
theory—so different that the fundamental problem which is shown to be
inexpressible in FPC, distinguishing $\mathcal{G}(U_{1})$ from
$\mathcal{G}(U_{2})$, is not even $\mathsf{NP}$-hard.101010To see this,
observe that a given bundle of constraints in either structure is satisfiable
if and only if a certain system of $m-\ell$ linear equations over
$\mathbb{F}_{2}^{m}$ is solvable. In $\mathcal{G}(U_{1})$, the union of all of
these systems is completely satisfiable, while in $\mathcal{G}(U_{2})$, they
are not, so distinguishing $\mathcal{G}(U_{1})$ from $\mathcal{G}(U_{2})$ can
be accomplished by Gaussian elimination.

To prove the FPC-UGC in its entirety, it will be necessary to (almost
completely) eliminate the parallel, contradictory constraints between pairs of
vertices. These simple gadgets provide Duplicator with the power to make
choices, circumventing the “uniqueness” inherent in “Unique Games,” but they
kill the completeness of the inapproximability gap. One possible approach
would be to build larger gadgets with more complicated automorphisms achieving
a similar effect as these parallel constraints. We leave this possibility to
future work.

## Acknowledgments

This work was generously supported by the Winston Churchill Foundation through
a Churchill Scholarship at the University of Cambridge, UK. I would like to
express my deep gratitude to Anuj Dawar, whose advice and insights
substantially improved the results in this paper. I am also grateful to Neil
Immerman, as well as three anonymous LICS reviewers, for detailed, helpful
comments on earlier drafts.

## References

  * [ABD09] Albert Atserias, Andrei A. Bulatov, and Anuj Dawar.  Affine systems of equations and counting infinitary logic.  Theoretical Computer Science, 410(18):1666–1683, 2009.  doi:10.1016/j.tcs.2008.12.049.
  * [AD17] Matthew Anderson and Anuj Dawar.  On symmetric circuits and fixed-point logics.  Theory of Computing Systems, 60(3):521–551, 2017.  doi:10.1007/s00224-016-9692-2.
  * [AD19] Albert Atserias and Anuj Dawar.  Definable inapproximability: new challenges for duplicator.  Journal of Logic and Computation, 29(8):1185–1210, 2019.  doi:10.1093/logcom/exz022.
  * [AN01] André Arnold and Damian Niwinski.  Rudiments of $\mu$-calculus.  Elsevier, 2001.
  * [CFI89] Jin-yi Cai, Martin Fürer, and Neil Immerman.  An optimal lower bound on the number of variables for graph identification.  In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 612–617, 1989.  doi:10.1109/SFCS.1989.63543.
  * [Daw15] Anuj Dawar.  The nature and power of fixed-point logic with counting.  ACM SIGLOG News, 2(1):8–21, January 2015.  doi:10.1145/2728816.2728820.
  * [DKK+18] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  On non-optimally expanding sets in Grassmann graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940–951, 2018.  doi:10.1145/3188745.3188806.
  * [DW17] Anuj Dawar and Pengming Wang.  Definability of semidefinite programming and Lasserre lower bounds for csps.  In 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, June 20-23, 2017, pages 1–12, 2017\.  doi:10.1109/LICS.2017.8005108.
  * [GT18] Joshua A. Grochow and Jamie Tucker-Foltz.  Computational topology and the unique games conjecture.  In 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, pages 43:1–43:16, 2018.  doi:10.4230/LIPIcs.SoCG.2018.43.
  * [Hel96] Lauri Hella.  Logical hierarchies in PTIME.  Information and Computation, 129(1):1–19, 1996.  doi:10.1006/inco.1996.0070.
  * [Imm86] Neil Immerman.  Relational queries computable in polynomial time.  Information and Control, 68(1-3):86–104, 1986.  doi:10.1016/S0019-9958(86)80029-8.
  * [Kho10] Subhash Khot.  On the unique games conjecture (invited survey).  In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010, pages 99–121, 2010.  doi:10.1109/CCC.2010.19.
  * [KMS18] Subhash Khot, Dor Minzer, and Muli Safra.  Pseudorandom sets in Grassmann graph have near-perfect expansion.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592–601, 2018\.  doi:10.1109/FOCS.2018.00062.
  * [Kol11] Alexandra Kolla.  Spectral algorithms for unique games.  Computational Complexity, 20(2):177–206, 2011.  doi:10.1007/s00037-011-0011-7.
  * [KPS10] Subhash Khot, Preyas Popat, and Rishi Saket.  Approximate Lasserre integrality gap for unique games.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010\. Proceedings, pages 298–311, 2010.  doi:10.1007/978-3-642-15369-3\\_23.
  * [Lib04] Leonid Libkin.  Elements of Finite Model Theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2004\.  URL: http://www.cs.toronto.edu/%7Elibkin/fmt, doi:10.1007/978-3-662-07003-1.
  * [LUW94] Felix Lazebnik, V. Ustimenko, and Andrew Woldar.  A new series of dense graphs of high girth.  Bulletin of the American Mathematical Society, 32, 12 1994.  doi:10.1090/S0273-0979-1995-00569-0.
  * [Ott97] Martin Otto.  Bounded variable logics and counting - a study in finite models, volume 9 of Lecture Notes in Logic.  Springer, 1997.
  * [OW12] Ryan O’Donnell and John Wright.  A new point of NP-hardness for unique games.  In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, pages 289–306, 2012.  doi:10.1145/2213977.2214005.
  * [Rag09] Prasad Raghavendra.  Approximating NP-Hard Problems Efficient Algorithms and Their Limits.  PhD thesis, University of Washington, USA, 2009.  AAI3377316.
  * [TF20] Jamie Tucker-Foltz.  Approximating Constraint Satisfaction Problems Symmetrically.  Master’s thesis, University of Cambridge, UK, 2020.
  * [Var82] Moshe Y. Vardi.  The complexity of relational query languages (extended abstract).  In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 137–146, 1982\.  doi:10.1145/800070.802186.