# List Agreement Expansion from Coboundary Expansion

Roy Gotlib 111Department of Computer Science, Bar-Ilan University,
<EMAIL_ADDRESS>research supported by ERC.  Tali Kaufman 222Department
of Computer Science, Bar-Ilan University<EMAIL_ADDRESS>research supported
by ERC and BSF.

###### Abstract

One of the key components in PCP constructions are agreement tests. In
agreement test the tester is given access to subsets of fixed size of some
set, each equipped with an assignment. The tester is then tasked with testing
whether these local assignments agree with some global assignment over the
entire set. One natural generalization of this concept is the case where,
instead of a single assignment to each local view, the tester is given access
to $l$ different assignments for every subset. The tester is then tasked with
testing whether there exist $l$ global functions that agree with all of the
assignments of all of the local views. In this work we present sufficient
condition for a set system to exhibit this generalized definition of list
agreement expansion. This is, to our knowledge, the first work to consider
this natural generalization of agreement testing.

Despite initially appearing very similar to agreement expansion in definition,
proving that a set system exhibits list agreement expansion seem to require a
different set of techniques. This is due to the fact that the natural
extension of agreement testing (i.e. that there exists a pairing of the lists
such that each pair agrees with each other) does not suffice when testing for
list agreement as list agreement crucially relies on a global structure. It
follows that if a local assignments satisfy list agreement they must not only
agree locally but also exhibit some additional structure. In order to test for
the existence of this additional structure we use the connection between
covering spaces of a high dimensional complex and its coboundaries.
Specifically, we use this connection as a form of “decoupling”.

Moreover, we show that any set system that exhibits list agreement expansion
also supports direct sum testing. This is the first scheme for direct sum
testing that works regardless of the parity of the sizes of the local sets.
Prior to our work the schemes for direct sum testing were based on the parity
of the sizes of the local tests.

##  1 Introduction

#### Agreement testing

is an important tool that is central to many PCP constructions. In agreement
testing one is given access to a set of functions
$\left\\{f_{s}\right\\}_{s\in S}$ that are thought of as “local views” of some
global function $F:\bigcup_{s\in S}{s}\rightarrow\left\\{0,1\right\\}$. These
are local views in the sense that every $f_{s}$ is a function
$f_{s}:s\rightarrow\left\\{0,1\right\\}$ and for every $s$: $F|_{s}=f_{s}$. If
a set of local functions $\left\\{f_{s}\right\\}_{s\in S}$ meets the above
criterion we call that set an agreeing set of functions. An agreement test is
a probabilistic algorithm that picks two sets $s_{1},s_{2}$ of size $k$ that
intersect each other on $\xi$ elements and checks whether
$f_{s_{1}}|_{s_{1}\cap s_{2}}=f_{s_{2}}|_{s_{1}\cap s_{2}}$. A structure is
said to support agreement testing (alternatively, a structure is an agreement
expander) if the following two properties hold:

  1. 1.

The agreement test always accepts agreeing sets of functions.

  2. 2.

If the agreement test rejects a set with probability $\varepsilon$ then there
is a global function that disagrees with at most
$O\left(\frac{1}{1-\frac{\xi}{k}}\varepsilon\right)$ of the local functions.

Most works that pertain to agreement testing are interested in the case where
the intersection between sets is small, specifically $\xi=\frac{k}{2}$. This
is because in those cases the proportion between $k$ and $\xi$ is constant and
any local assignment that is rejected with probability $\epsilon$ has a global
assignment which disagrees with $O(\epsilon)$ of the local assignments. In
this work, however, we are interested in a slightly different definition of
agreement expansion called _$1$ -up agreement expansion_. In $1$-up agreement
the intersection between pairs of sets contain all but one element from each
set (i.e. $\xi=k-1$). Also note that many complexes (and even some sparse
complexes [DK17]) exhibit $1$-up agreement expansion (as well complexes such
as the complete complex).

In [DK17] Dinur and Kaufman proved that some high dimensional expanders
support agreement testing and term these _agreement expanders_. Since then
agreement expanders have proven to be extremely useful in various contexts:
From derandomization for direct product testing [DK17] to conversion of local
tests to robust tests [DHKRZ18] and others (for more examples see [DDHRZ20,
DDFH18]).

#### List agreement expansion

In this paper we present a new, natural generalization of agreement testing in
which, instead of being given a single function for each set $s$, we are given
a list of $l$ functions and we want to test whether these functions are local
views of $l$ global functions (where $l$ is some constant). By that we mean
that there exist $l$ global functions $F_{1},\cdots,F_{l}:\bigcup_{s\in
S}{s}\rightarrow\left\\{0,1\right\\}$ and a permutation $\pi_{s}$ for every
$s$ such that every local view $f_{s}^{i}:s\rightarrow\left\\{0,1\right\\}$
agrees with the global function $F_{\pi(i)}$ (i.e.
$F_{\pi(i)}|_{s}=f_{s}^{i}$). In this paper we ask whether there are
structures that support list agreement tests. We term such structures _list
agreement expanders_.

######  Definition 1.1 (List Agreement expansion, informal. For formal see
2.24).

We say that a set system exhibits list agreement expansion if there exists a
tester that, given access to a set of assignments
${\mathscr{{F}}}=\left\\{{\mathscr{{F}}}^{s}_{i}\right\\}_{s\in
S,i\in\left[l\right]}$ such that
${\mathscr{{F}}}^{s}_{i}:s\rightarrow\left\\{0,1\right\\}$, queries $Q$ of the
local assignments333The algorithm queries one of the local assignments in one
of the lists.
${\mathscr{{F}}}^{s_{1}}_{i_{1}},\cdots,{\mathscr{{F}}}^{s_{Q}}_{i_{Q}}$ and
accepts or rejects such that the following holds:

  1. 1.

Always accepts if there exists $l$ functions $F_{1},\cdots,F_{l}:\bigcup_{s\in
S}{s}\rightarrow\left\\{0,1\right\\}$ and a permutation $\pi_{s}$ for every
$s$ such that every local view $f_{s}^{i}:s\rightarrow\left\\{0,1\right\\}$
agrees with the global function $F_{\pi_{s}(i)}$ (i.e.
$F_{\pi_{s}(i)}|_{s}=f_{s}^{i}$).

  2. 2.

If the tester rejects with probability $\epsilon$ then $O(\epsilon)$ of the
assignment in ${\mathscr{{F}}}$ can be changed such that the property stated
above will hold.

#### List agreement testing compared to agreement testing

At first list agreement testing might seem fairly reminiscent of agreement
testing and, while the definitions are similar, list agreement testing seem to
require different tools altogether. In the list agreement testing paradigm one
is not only concerned with having agreement between local assignments, but
also that these agreements are structured in the right way. One key example of
agreements that are not well structured is the following: Consider a cycle of
odd length with the following $2$-assignments on every edge:
${\mathscr{{F}}}^{\left\\{u,v\right\\}}=\left\\{\left[u=1,v=0\right],\left[u=0,v=1\right]\right\\}$.
Note that any two edges that share a vertex agree on the intersection444In the
sense that there is a permutation $\pi$ such that the $i$-th assignment of one
of the faces agrees with the $\pi(i)$-th assignment of the other.. That being
said, ${\mathscr{{F}}}$ is not agreeing (since if it was an agreeing
assignment the graph would be bi-partite555One can interpret the local lists
as “$u$ and $v$ are on different sides of the graph”.).

#### Conditions under which list agreement testing is possible

As we discussed, list agreement not only requires agreement but also some
additional structure. We will show that this additional structure comes in the
form of _coboundary expansion_ \- A topological notion of expansion. Our
construction of a list agreement tester will rely on coboundary expansion as a
way to decouple the $l$ instances of agreement testing and then use agreement
expansion in order to achieve local agreement. We found that the global
structure required in order to have $l$ global cochains is, in a sense,
equivalent to a coboundary of a different complex. That complex is induced by
the original complex and the agreement test. We show that that the
coboundaries on the induced complex are testable using the fact that the
original complex is _both_ a coboundary expander and a $1$-up agreement
expander. Effectively, we use the coboundary expansion in order to derive the
_global_ structure (i.e. that the local agreements can indeed be “glued
together” into $l$ global functions) while using the agreement expansion in
order to derive the _local_ structure (i.e. that the local agreements agree
with each other).

As we previously hinted at, list agreement offers a very descriptive language
which can, at times, be considerably richer than regular agreement. This
richer structure allows us to, for example, describe the question of whether a
subgraph666Here a subgraph is determined by picking a subset of the vertices
and all the edges that connect them. of the complex’s underlying graph is two
sided or not. One such subgraph of particular interest is a cycle as list
agreement allows us to describe the question of whether a cycle is of odd
length merely by knowing which vertices are a part of the cycle. This, in
effect, yields a non-constant lower bound on the number of queries required in
order to test list agreement in the general case as testing whether a cycle is
odd cannot be done locally (More details on this can be found in Section 7).

In order to overcome this limitation we introduce a restriction on list
agreement. Namely, we require that the local assignments given to each set
have some small distance separating them. Using this small distance we show
that testing list agreement is possible with a constant number of queries.

Now that we have an understanding of list agreement expansion we can present
our main theorem:

######  Theorem 1.2 (Main Theorem, informal. For formal see 6.1).

Any simplicial complex that has sufficient expansion properties (namely
coboundary expansion and a $1$-up agreement expansion) supports list agreement
testing using $3l$ queries777The test queries all the local assignments of
three faces. (where $l$ is the length of the list) under small distance
assumptions on the local assignments888More specifically we assume that the
local assignments differ on at least two vertices. This assumption cannot be
removed in the domain of complexes that we examine, see Section 7..

It is important to note that there are simplicial complexes who meet the
Theorem’s criteria. For example, the spherical buildings and the complete
complex have sufficient expanding conditions for Theorem 1.2 (See [DM19] and
[KM20]).

#### Direct sum testing

Another natural (and extremely useful) construction in hardness amplification
is the direct sum.

######  Definition 1.3 (Direct sum).

Given a function $f:S\rightarrow\left\\{0,1\right\\}$ (where $S$ is an
arbitrary set) its $k$-fold direct sum is a function
$F:\binom{S}{k}\rightarrow\left\\{0,1\right\\}$ such that: $F(A)=\sum_{a\in
A}{f(a)}$.

Direct sums are useful in a variety of contexts, from Yao’s XOR Lemma [Yao82]
which states that if a function is hard to approximate then its direct sum is
exponentially harder, to the hardness of approximation of problems in
$P^{NP}\parallel$999$P^{NP}\parallel$ is the set of problems that can be
solved in polynomial time with oracle access to a problem in $NP$ such that
all the queries to the oracle are performed in parallel. [IJK09].

#### A unified framework for direct sum testing

It is natural to ask how, given a function, can one make sure that it is
indeed a direct sum in a derandomized fashion. There have been several works
on derandomizing direct sum testing [DDG+17, GK19] but the tests presented in
them for constant values of $k$ were heavily dependent on the parity of $k$.
In this work, we show how to use list agreement expanders in order to provide
a new natural test for whether a function $F$ is a direct-sum (while having
stronger assumptions on the expansion of the complex). Our testing framework
is the first that can be applied to any value of $k$ regardless of its parity.
In addition, our framework shaves off an $O(k)$ factor in the query complexity
for the case when $k$ is odd (compared to [GK19]). Specifically we show that:

######  Theorem 1.4 (Testability of Direct Sums, informal. For formal see
Theorem 8.10).

Any simplicial complex that supports list agreement testing supports direct
sum testing, regardless of the parity of $k$.

###  1.1 High Dimensional Expansion Toolset

We will now move on to presenting the main toolset we use in the proof:

#### Simplicial complexes

are generalizations of graphs to higher dimensions. A simplicial complex is a
hyper-graph with closure property, i.e. if ${\sigma}$ is a hyper-edge then any
subset of ${\sigma}$ is also an hyper-edge in the hyper-graph. We term the
hyper-edges of a simplicial complex as its faces and define the dimension of a
face ${\sigma}$ to be $\left|{\sigma}\right|-1$. We denote the set of $i$
dimensional faces by $X(i)$. We also define the dimension of a simplicial
complex as the dimension of its maximal face. For example, any non-empty graph
is a $1$-dimensional simplicial complex101010We add the empty face to the
graph., its vertices are the $0$-dimensional faces and edges are its
$1$-dimensional faces. Note that in connected graphs all of the maximal faces
are of the same dimension as every vertex is part of an edge (otherwise there
exists an isolated edge and the graph is not connected), when this holds we
say that complex is _pure_. We limit our discussion to pure simplicial
complexes. It is often convenient to think of high dimensional faces as
geometrical shapes, for example we think of a $2$-dimensional face as a
triangle, a $3$-dimensional face as a pyramid etc. In many cases we will be
interested in weighted simplicial complexes. In weighted simplicial complexes
a weight function is given to the top dimensioanl faces. This weight function
is positive and sums up to $1$. The weight of lower dimensional faces is
determined by the weight of the top dimensional faces in which they are
contained. It is important to note that even if the top dimensioanl faces all
have the same weight, the same does not necessarily hold for faces of a lower
dimension.

#### High dimensional expanders

are generalizations of one-dimensional expanders (i.e. graph expanders) to
higher dimensions. Unlike the one dimensional case, there are multiple
definitions for the notion of expansion in higher dimensions. Moreover, the
connections between the various generalizations of expansion is unknown. In
this work we will use two of these definitions: _coboundary expansion_ and
_agreement expansion_. We are going to think of both definitions of expansion
as measures of how well certain properties can be tested on the complex.

#### Coboundary expansion

is a natural generalization of the combinatorial expansion to higher
dimensions. Specifically, one dimensional expansion can be thought of how well
the following test tests whether a cut in the graph is trivial: Pick a random
edge and accept iff it does not cross the cut. Note that this corresponds
directly with the graph’s cheeger constant as the cut can be thought of as a
set and the number of edges that cross the cut are exactly the outgoing edges
of the set. Therefore the cheeger constant of the graph determines _exactly_
how well the test performs. Coboundary expansion is a generalization of the
cheeger constant that includes the second dimension as well. In the second
dimension the property being tested is whether a given subset of edges
represents a cut (i.e. whether there is an underlying cut such that an edge is
in the set iff it crosses the cut). The test being measured is the test that
picks a triangle and accepts if the number of edges that are both in the set
and the triangle is even. In a coboundary expander both tests (i.e. the test
in the first and second dimensions) have a large distance (larger than some
constant).

#### Agreement expanders

are (possibly sparse) simplicial complexes and a distribution $\mathcal{D}$ on
the $k$-dimensional faces such that, for any set of assignments to the
$k$-dimensional faces of the simplicial complex, if most pairs
${\sigma}_{1},{\sigma}_{2}\sim\mathcal{D}$ agree on their intersection then
the local assignments are close to agreeing with some global assignment (for
any $k$). In this work we are going to use a strengthening of agreement
expansion, namely _$1$ -up agreement expanders_, $1$-up agreement expanders
are agreement expanders where the distribution $\mathcal{D}$ matches the
procedure of picking a $\left(k+1\right)$-dimensional face and then randomly
selecting two $k$-faces that are contained in it. In [DK17] Dinur and Kaufman
show that there exists a family of bounded degree $1$-up agreement expanders.

#### Covers

of a simplicial complex $X$ are simplicial complexes ${Y}$ that, for every
vertex ${v}$ of $X$ contain $l$ vertices $[{v},1],\dots,[{v},l]$, In addition,
${\sigma}=\left({v}_{1},\dots,{v}_{i}\right)$ is a face in $X$ iff ${Y}$ has
$l$ disjoint faces of the form
$\left([{v}_{1},j_{1}],\dots,[{v}_{i},j_{i}]\right)$. For example: a $2$-cover
of a $1$-dimensional complex (i.e. a graph) has, for every vertex ${v}$, two
vertices $[{v},0],[{v},1]$. In addition, for every edge $\left({v},{u}\right)$
in the graph the cover has two edges, either
$\left([{v},0],[{u},0]\right),\left([{v},1],[{u},1]\right)$ or
$\left([{v},0],[{u},1]\right),\left([{v},1],[{u},0]\right)$. In this work we
are going to discuss a special subset of the covering spaces of a simplicial
complex. Specifically we are going to be interested in the trivial covering
spaces that are comprised of $l$ disjoint copies of the original complex. We
end our discussion of covering spaces by noting that the definition of a cover
applies to general topological spaces and not necessarily to simplicial
complexes.

#### Near Covers

are spaces that are close to being covering spaces of a given simplicial
complex. Near covers are a relaxation of covers where only the first two
dimensions are required to be covered properly. More specifically, every
vertex ${v}$ is covered by $l$ vertices and every edge
$\left\\{{v},{u}\right\\}$ is covered by $l$ edges. The higher dimensional
faces are only covered if the lower dimensioanl faces are structured in a way
that allows them to be covered. For example consider a simplicial complex
comprised of a single two dimensional face
$\left\\{{v}_{1},{v}_{2},{v}_{3}\right\\}$. Consider the near cover of said
complex whose $1$-dimensioanl faces are the following cycle of length $6$:

$\left\\{\left\\{\left[{v}_{1},0\right],\left[{v}_{2},0\right]\right\\},\left\\{\left[{v}_{2},0\right],\left[{v}_{3},0\right]\right\\},\left\\{\left[{v}_{3},0\right],\left[{v}_{1},1\right]\right\\},\left\\{\left[{v}_{1},1\right],\left[{v}_{2},1\right]\right\\},\left\\{\left[{v}_{2},1\right],\left[{v}_{3},1\right]\right\\},\left\\{\left[{v}_{3},1\right],\left[{v}_{1},0\right]\right\\}\right\\}$

Note that every vertex and every edge are covered and yet the single
$2$-dimensional face is not and thus this is a near cover that is not a cover.
It is important to note that every cover is a near cover and that sometimes
_genuine cover_ is used instead of cover to emphasize that a near cover is
indeed a cover.

###  1.2 Proof Strategy

In this work we are interested in testing whether a set system $S$ exhibits
list agreement expansion. Agreement expansion stems directly from the rapid
convergence of random walk that spectral expanders exhibit. While we still
test for agreement (and therefore require the same spectral expansion
assumptions on our set system) we also recall that list agreement requires
some additional structure over agreement. Specifically, not only does list
agreement require local agreement it also requires the local agreements to
exist in such a way that $l$ different global functions are formed.

Let us now characterize this additional structure further. Consider a set of
assignments ${\mathscr{{F}}}$ that gives every set $s$ in the set system a set
of $l$ assignments ${\mathscr{{F}}}^{s}_{1},\cdots,{\mathscr{{F}}}^{s}_{l}$.
For ease of presentation, allow us also to assume that for every two sets in
the set system $s,s^{\prime}$ there exists a unique permutation
$\pi_{s,s^{\prime}}$ such that ${\mathscr{{F}}}^{s}_{i}|_{s\cap
s^{\prime}}={\mathscr{{F}}}^{s^{\prime}}_{\pi_{s,s^{\prime}}(i)}|_{s\cap
s^{\prime}}$. Consider the following definition:

######  Definition 1.5 (Coboundary structure).

Let $A\subseteq\binom{S}{2}$ and let $G$ be a group. We say that a function
$f:A\rightarrow G$ has coboundary structure over $A$ with coefficients in $G$
if there exists $g:S\rightarrow G$ such that:

$f(a,b)=g(b)\left(g(a)\right)^{-1}$

We will show that, regardless of the set $A$, ${\mathscr{{F}}}$ exhibits list
agreement iff $f(s,s^{\prime})=\pi_{s,s^{\prime}}$ has a coboundary structure
with coefficients in $S_{l}$ (the symmetric group with $l$ elements). Recall
${\mathscr{{F}}}$ exhibits list agreement if there exists $l$ global functions
${\mathcal{{F}}}_{1},\cdots,{\mathcal{{F}}}_{l}$ and, for every set $s$ there
exists a permutation $\pi_{s}$ such that
${\mathscr{{F}}}^{s}_{i}={\mathcal{{F}}}_{\pi_{s}(i)}|_{s}$. It is easy to see
that in this case
$\pi_{s,s^{\prime}}=\pi_{s^{\prime}}\left(\pi_{s}\right)^{-1}$. In addition,
if $f(s,s^{\prime})$ has a coboundary structure then there exists $g$ such
that $f(a,b)=g(b)\left(g(a)\right)^{-1}$. In that case, the global functions
${\mathcal{{F}}}_{i}({v})$ can be calculated by picking any set $s$ that
contains ${v}$ and setting
${\mathcal{{F}}}_{i}({v})={\mathscr{{F}}}^{s}_{g(s)(i)}({v})$. We are
therefore interested in finding out if the permutations $\pi_{s,s^{\prime}}$
exhibit a coboundary structure.

Alas the fact that two local lists of assignments agree with each other under
some permutation does not necessarily mean that the permutation remains the
same when correcting $f$ so that it exhibits coboundary structure (even if
there is only one permutation that causes agreement). It is therefore natural
to ask “ _how far are $\pi_{s,s^{\prime}}$ from exhibiting a coboundary
structure?_”. This is _exactly_ what coboundary expansion with coefficients in
$S_{l}$ measures.

Then, after we have corrected the function $f$ so that it exhibits a
coboundary structure, we might have ruined some of the agreement we started
with. We will note, however, that now we have $l$ _independent_ instances of
an agreement problem (One for each
$\left\\{{\mathscr{{F}}}^{s}_{g(s)(i)}\right\\}_{s\in S}$, where
$g:S\rightarrow S_{l}$ such that
$f(s,s^{\prime})=g(s^{\prime})\left(g(s)\right)^{-1}$). We use the agreement
expansion to resolve those.

To conclude, we use spectral expansion in order to derive the agreement and
topological expansion in order to derive this additional structure.

###  1.3 Proof Layout

We start by assuming that the complex is a $1$-up agreement expander and
therefore the $1$-up test is a good agreement test. We then model the choices
done by the $1$-up agreement test as a simplicial complex which we dub “the
representation complex”. The modeling is done in the following way: The
vertices of the new complex will correspond to the $k$-dimensional faces of
the original complex. The edges of the new complex will correspond to the
choices done by the $1$-up agreement test (i.e. if a pair of faces
${\sigma}_{1},{\sigma}_{2}$ are chosen with some probability then there is an
edge between ${\sigma}_{1}$ and ${\sigma}_{2}$). We will construct the higher
dimensional faces of the representation complex so that the weight of the an
edge $({\sigma}_{1},{\sigma}_{2})$ in the representation complex will
correspond with the probability that the pair ${\sigma}_{1},{\sigma}_{2}$ is
chosen by the $1$-up agreement tester (see Definition 3.2 for a formal
definition). Note that the edges of the representation complex can be thought
of as the set $A$ from Definition 1.5. We will therefore be interested in
examining the expansion properties of the second dimension of the
representation complex. Alas, the representation complex is not a coboundary
expander but it does have a structure that facilitates bounding the distance
of a cochain from being a coboundary using a local property (see Appendix A
for more details).

Before we move on we note that the function $f$ from Definition 1.5 can be
thought of as a description of a near cover of the representation complex in
the following way: Every vertex ${v}$ is covered by $\left|G\right|$ elements
-
$\left\\{\left[{v},1\right],\cdots,\left[{v},\left|G\right|\right]\right\\}$.
The edges are described by the function $f$ in the following way: If ${v}$ and
${u}$ are connected in the original complex then $\left[{v},i\right]$ and
$\left[{u},f\left(\left\\{{v},{u}\right\\}\right)(i)\right]$ are connected in
the near cover. In order to simplify the presentation of the rest of the proof
we are going to use the language of near covers. It is important to note that
it is equivalent to the presentation in the proof strategy.

We start by showing how to relate any $l$-assignment whose local assignments
are sufficiently differing to an $l$-near-cover of the representation complex.
Specifically, every one of the local assignments to ${\sigma}$ in the
$l$-assignment will correspond to a vertex that covers ${\sigma}$ and two
vertices in the cover are connected if the assignments they correspond to
agree on their intersection (and, of course, if the edge that they cover
exists in the representation complex). Unlike the assumption in the proof
strategy, we cannot assume that every pair of lists agree with each other. We
therefore cover every edge $({v}_{1},{v}_{2})$ whose assignments do not agree
with each other using some fixed matching between the vertices that cover
${\sigma}_{1}$ and ${\sigma}_{2}$. Full details of this construction can be
found in Section 5.

Now that we have constructed the near cover we want it to have the additional
structure that we presented in the proof strategy. We note that a near cover
exhibits the additional structure we are interested in iff it corresponds to a
coboundary. We also note that the near cover corresponds to a coboundary iff
it is a genuine cover that is comprised of $l$ distinct copies of the original
complex. We use the connection between cochains and near covering spaces as
well as the result from Appendix A to show that it is possible to bound the
distance of the near cover we constructed from being comprised of $l$ distinct
copies of the original complex. Consider now a corrected version in the near
cover. While now we have the additional structure we are interested in, we
still have not gotten the agreement we are interested in.

Assume for now that we can query this genuine cover directly (which we cannot
as we only have access to a near cover that is close to it). In the genuine
cover, each of the copies of the original cover has an associated assignment
to its $k$-faces (since every vertex in the cover is associated with a single
local assignment to the face it represents). Consider running the $1$-up
agreement test on each of the copies of the representation complex with its
associated assignments. The test picks a $(k+1)$-face ${\sigma}$ and two of
its $k$-sub-faces ${\sigma}_{1},{\sigma}_{2}$, it then queries the local
assignment of these $k$-faces and accepts iff they agree on their
intersection. Another way of looking at the test is that it samples an edge
$e$ in the representation complex and accepts iff the faces represented by the
vertices in the edge agree on their intersection. We can therefore bound the
distance of the set of assignments from agreeing using the agreement expansion
of the original complex.

Alas we cannot query the genuine cover directly. We can, however, bound from
above the probability that the agreement test would reject had we ran it on
that genuine cover. Recall the construction of the near cover and note that if
$e$ was covered by edges that represent agreement in the original near cover
and, in addition, the cover of $e$ was not changed then the assignments to
both sides of $e$ agree on their intersection. Therefore the agreement test
would only reject if it picked an edge that had no agreement in the first
place or an edge that was changed when the near cover was corrected. Note that
the norm of the edges that satisfy these properties can be derived locally by
querying the lists of assignments - the former by observing whether there is
an agreement and the latter due to the testability of coboundaries in the
representation complex. We use this in order to bound the distance of any
$l$-assignment from being an agreeing $l$-assignment.

Before we move on we wish to emphasise how the covering spaces allow us to
decouple dependencies. Consider the near covering space of the representation
complex. In an ideal case, the near cover induced by the $l$-assignment is a
genuine cover that corresponds to a coboundary. In such cases the cover is
comprised of $l$ independent copies of the original complex and we can run the
agreement test $l$ times independently and get the distance of the
$l$-assignment from agreeing. In most cases, however, the near cover induced
by the $l$-assignment is not a genuine cover that corresponds to a coboundary.
In these cases the copies of the complex are dependent on each other in the
sense that what would have been copies of the original complex are now
connected via various edges. A crucial step in the test we propose involves
“decoupling” these dependencies. We will show that, despite the fact that the
representation complex’s cohomology does not vanish, the coboundaries of the
representation complex are still locally testable. Using this test we can
bound the distance of the $l$-assignment from inducing independent instances
of agreement testing. We believe that the technique of modeling objects of
interest as near covers of a coboundary expander could be a useful measure of
dependency as not only does it bound the distance of the object from being
independent but it is also locally testable.

###  1.4 Related Work

Agreement testing is an inherit part of most PCP constructions as well as
various other applications and were extensively studied in the past few years
(for examples, see [DK17, DD19, DFH19, DKK+18, BKS18, KMS17, DFH17]). In
recent years a connection between high dimensional expanders and agreement
testing was established: In [DK17] Dinur and Kaufman defined the notion of
agreement expanders described above. Later Kaufman and Mass presented in
[KM20] a new method for constructing agreement expanders. In this work we
generalize the notion of agreement expanders to the case where each face has
$l$ local assignments. The goal in this new setting is to check whether there
exists $l$ global functions that match all the local assignments (for formal
definition see 2.21).

In order to provide said generalization we use the connection between cocycles
and cover spaces of simplicial complexes. The connection between cocycles and
cover spaces of a simplicial complex was first introduced in [Sur84]. Then in
[DM19] Dinur and Meshulam defined the notion of cover stable complexes which
are complexes where if a near cover satisfies most local conditions then it is
close to a genuine cover. They then show that a simplicial complex is cover
stable if and only if it is an expanding with respect to non-abelian
cohomology. We use the connection between covers of high dimensional expanders
and their cocycles in a new way: Specifically, we use the structure of covers
that correspond with coboundaries in order to untangle the near cover into
disjoint copies of the original complex.

Direct sums are natural construction in hardness of approximation. A function
$F:\binom{[n]}{k}\rightarrow\left\\{0,1\right\\}$ is a $k$-direct-sum of
$f:[n]\rightarrow\left\\{0,1\right\\}$ if for every
${\sigma}\in\binom{[n]}{k}$ it holds that
$F({\sigma})=\sum_{{v}\in{\sigma}}{{v}}$. Testing direct sums is a problem
that was extensively studied in recent years. The first connections between
testing direct sums and high dimensional expanders was presented in [KL14] in
which Kaufman and Lubotzky presented a test for the case of $k=2$. Later in
[DDG+17] (and generalized to high dimensional expanders in [DK17]) a test for
constant even values of $k$ was found. This test, however, could not deal with
the case where $k$ is odd due to inherit limitations. After that, another test
was proposed by Gotlib and Kaufman in [GK19]. Their test could deal with the
case where $k$ is an odd constant, however there seem to be no simple way of
extending their setting to the case where $k$ is even. In this work we use
list agreement expanders in order to present the first test for direct sums
for constant values of $k$ regardless of its parity.

###  1.5 Paper Organisation

We will start by defining the notions of high dimensional expansion we use
throughout the paper in Section 2. In addition to that Section 2 includes a
formal definition of list agreement expansion and the distance measure we are
going to use. Then, in section 3, we present the representation complex in
depth - we characterize its structure and expansion properties as well as its
cover stability. In section 4 we present properties of covers that correspond
to coboundaries111111This section is completed by Appendix A in which we show
that the coboundaries are testable in the representation complex.. We then
move on to show how assignments to the original complex imply a near cover for
the representation complex in section 5. After that we show how to use the
cover stability of the representation complex in order to show that the
complex is a list agreement expander in section 6. We then show how to use
list agreement expanders in order to provide a test for $k$-direct-sum that is
independent of the oddity of $k$ (in section 8). In Section 7 we discuss the
$2$-differing assumption further and show that without the $2$-differing
assumption there are some complexes of interest (for example, the spherical
buildings) in which there are no tests for list agreement that perform a
constant number to queries. Then we show a lower bound to the number of
queries required for list agreement in Appendix B.

##  2 Preliminaries

###  2.1 Simplicial Complexes

As we stated before, the generalization of graphs we will be using are
simplicial complexes, which we will now present more thoroughly:

######  Definition 2.1 (Simplicial complex).

A simplicial complex $X$ is set of sets such that if ${\sigma}\in X$ then
every ${\sigma}^{\prime}\subseteq{\sigma}$ is also in $X$. Each of the sets in
$X$ are termed the faces of $X$.

######  Note.

The faces of a simplicial complex have an orientation. The orientation must be
consistent in the sense that there is an ordering of the $0$-dimensional faces
that determines the orientation of all the faces in higher dimensions. In the
vast majority of this paper the orientation is irrelevant to the arguments and
therefore we will ignore it for the most part. When we are forced to consider
the orientation of a face ${\sigma}=\left\\{{v}_{0},\dots,{v}_{i}\right\\}$ we
will denote the face with round brackets (i.e.
${\sigma}=\left({v}_{0},\dots,{v}_{i}\right)$)

Let us also define the dimension of a face and the dimension of the complex

######  Definition 2.2 (Dimensions).

Let $X$ be a simplicial complex. Define the dimension of a face ${\sigma}\in
X$ to be $\dim({\sigma})=\left|{\sigma}\right|-1$. Also, denote the set of
faces of dimension $i$ by $X(i)$ In addition, define the dimension of the
simplicial complex $X$ to be:

$\dim(X)=\max_{{\sigma}\in X}\left(\dim\left({\sigma}\right)\right)$

######  Definition 2.3 (Pure simplicial complex).

A simplicial complex is called pure if all of its maximal faces are of the
same dimension.

From this point onwards we limit our discussion to pure simplicial complexes
(and whenever we refer to a simplicial complex we will actually refer to a
pure simplical complex). A standard weight function is defined over the
various faces of a simplicial complex which we will present below:

######  Definition 2.4 (Weight function).

Let $X$ be a $d$ dimensional simplicial complex. Define the weight of a face
${\sigma}\in X$ as the fraction of maximal faces in $X$ that contain
${\sigma}$. Formally:

$\operatorname{w}_{X}\left({\sigma}\right)=\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{d+1}{\left|{\sigma}\right|}\left|X(d)\right|}$

When the complex is clear from context we will omit it from the notation.

Note that this weight function can be thought of as a probability distribution
over the faces of each dimension (and indeed we will think of it as such).
Moreover there is a way to sample a face with the probability distribution
defined by the weight. We can also use this weight function to define the
following norm over sets of faces:

######  Definition 2.5 (Norm on faces).

Let $X$ be a $d$-dimensional simplicial complex, let $-1\leq i\leq d$ and also
let $S\subseteq X(i)$. Define the norm of $S$ in $X$ to be:

$\left\|S\right\|_{X}=\sum_{{\sigma}\in
S}{\operatorname{w}_{X}\left({\sigma}\right)}$

When the complex is clear from context we will omit it from the notation.

In many cases it is helpful to consider all the faces of higher dimension that
contain a face from a set of faces $S$. In order to do that we are going to
use the containment operator defined below:

######  Definition 2.6 (Containment operator).

Let $X$ be a $d$-dimensional simplicial complex, let $-1\leq i\leq j\leq d$
and also let $S\subseteq X(i)$. Define the following:

$\operatorname{\Gamma}^{j}(S)=\left\\{{\tau}\in X(j)\middle|\exists{\sigma}\in
S:{\sigma}\subseteq{\tau}\right\\}$

There is also a connection between $\left\|S\right\|$ and
$\left\|\operatorname{\Gamma}^{k}(S)\right\|$ depicted in the following fact:

######  Fact 2.7.

Let $X$ be a $d$-dimensional simplicial complex, let $-1\leq i\leq j\leq d$
and also let $S\subseteq X(i)$ then:

$\left\|S\right\|\leq\left\|\operatorname{\Gamma}^{j}(S)\right\|\leq\binom{j+1}{i+1}\left\|S\right\|$

We will now introduce the notions of cochains, cocycles and coboundaries which
are natural spaces of functions over any given simplicial complex:

######  Definition 2.8 (Cochains).

Let $X$ be a simplicial complex and let $G$ be a group. Define the set of
$0$-cochains with coefficients in $G$ to be the set of functions from the
vertices of $X$ to $G$. In addition, denote the set of $0$-cochains with
coefficients in $G$ by $C^{0}\left(X;G\right)$. Also, define the set of
$1$-cochains with coefficients in $G$ as the following set:

$C^{1}\left(X;G\right)=\left\\{{F}:X(1)\rightarrow
G\middle|{F}({v},{u})=\left({F}({u},{v})\right)^{-1}\right\\}$

We also define the following operators:

######  Definition 2.9 (Coboundary operators).

Define the operator $d_{-1}:C^{-1}\left(X;G\right)\rightarrow
C^{0}\left(X;G\right)$ to be:

$d_{-1}{F}(v)={F}(\emptyset)$

Define the operator $d_{0}:C^{0}\left(X;G\right)\rightarrow
C^{1}\left(X;G\right)$ to be:

$d_{0}{F}(u,v)={F}(u)\left({F}(v)\right)^{-1}$

Also define the operator $d_{1}$ such that for every cochain ${F}\in
C^{1}\left(X;G\right)$ and every $(u,v,w)\in X(2)$:

$d_{1}{F}(u,v,w)={F}(u,v){F}(v,w){F}(w,u)$

These operators define the following spaces over the first three dimensions of
the simplicial complex:

######  Definition 2.10 (Cocycles and coboundaries).

Let $X$ be a simplicial complex and $G$ a group, define the following spaces:

  * •

For $i\in\left\\{0,1,2\right\\}$ define the $i$ dimensional coboundaries:

$B^{i}\left(X;G\right)=\left\\{d_{i-1}{F}\middle|{F}\in
C^{i-1}\left(X;G\right)\right\\}$

  * •

For $i\in\left\\{0,1\right\\}$ define the $i$ dimensional cocycles:

$Z^{i}\left(X;G\right)=\left\\{{F}\in
C^{i}\left(X;G\right)\middle|d_{i}{F}=\mathbbm{1}\right\\}$

And, as with the cochains, when $G=\mathbbm{F}_{2}$ we omit $G$ from the
notation.

######  Note.

We only define these spaces in the first two dimensions because we are working
with a general group $G$ rather then an abelian group. If we assume that $G$
is an abelian group one can generalize the definition of cochains, cocycles
and coboundaries as well as the coboundary operators to higher dimensions.

Consider also the following:

######  Fact 2.11.

For every simplicial complex $X$ and group $G$:
$B^{i}\left(X;G\right)\subseteq Z^{i}\left(X;G\right)\subseteq
C^{i}\left(X;G\right)$

Of particular interest to our case are coboundaries with coefficients in the
symmetric group with $l$ elements that we denote $S_{l}$.

We also extend the norm defined in Definition 2.5 to a norm over the cochains:

######  Definition 2.12 (Norm of a cochain).

Let $X$ be a simplicial complex. For any ${F}\in C^{i}\left(X;G\right)$,
define the following norm:

$\left\|{F}\right\|_{X}=\left\|\left\\{{\sigma}\in
X(i)\middle|{F}({\sigma})\neq 1\right\\}\right\|$

When the complex is clear from context we will omit it from the notation.

This norm also defines a natural distance function between any two cochains:

######  Definition 2.13 (Distance between cochains).

Let ${F}_{1},{F}_{2}$ be two cochains in some simplicial complex $X$. Define
the distance between ${F}_{1}$ and ${F}_{2}$ to be:

$\operatorname{dist}\left({F}_{1},{F}_{2}\right)=\left\|{F}_{1}\left({F}_{2}\right)^{-1}\right\|$

It is also natural, given a simplicial complex, to describe the simplicial
complex that is constructed using only faces whose dimension is at most some
$i$. This is called the _skeleton_ of the simplicial complex and is formally
defined below:

######  Definition 2.14 (Skeleton).

Let $X$ be a simplicial complex. Define its $i$-th skeleton to be the
following simplicial complex:

$\left\\{{\sigma}\in X\middle|{{\sigma}}\leq i\right\\}$

It would also be useful to define local views of faces in a simplicial
complex. We call these local views _links_ and think of them as the faces seen
by a certain face.

######  Definition 2.15 (Link).

Let $X$ be a $d$-dimensional simplicial complex and let ${\sigma}\in X(i)$.
Define the link of ${\sigma}$ in $X$ as the following
$\left(d-i\right)$-dimensional simplical complex:

$X_{{\sigma}}=\left\\{{\tau}\setminus{\sigma}\middle|{\sigma}\subseteq{\tau}\text{
and }{\sigma}\in X\right\\}$

Note that the weight function of the faces in the link of a face ${\sigma}$ is
strongly connected to the weight of ${\sigma}$ and the weight function of the
original complex:

######  Lemma 2.16.

Let $X$ be a $d$-dimensional simplicial complex and let ${\sigma}$ be an
$i$-dimensional face. The weight of a $j$-dimensional face in the link of
${\sigma}$ is:

$\operatorname{w}_{X_{\sigma}}\left({\tau}\right)=\frac{\operatorname{w}_{X}\left({\tau}\cup{\sigma}\right)}{\binom{\left|{\sigma}\right|+\left|{\tau}\right|}{\left|{\tau}\right|}\operatorname{w}_{X}\left({\sigma}\right)}=\frac{\operatorname{w}_{X}\left({\tau}\cup{\sigma}\right)}{\binom{i+j+2}{j+1}\operatorname{w}_{X}\left({\sigma}\right)}$

We finish our presentation of simplicial complexes by defining isomorphic
simplicial complexes:

######  Definition 2.17 (Isomorphic simplicial complexes).

Let $X,{Y}$ be two simplicial complexes. We say that $X$ is isomorphic to
${Y}$ and denote $X\cong{Y}$ if there exists an invertible function
$f:{Y}\rightarrow X$ such that of every ${\sigma},{\tau}\in{Y}$ it holds that:

${\sigma}\subseteq{\tau}\Leftrightarrow f({\sigma})\subseteq f({\tau})$

###  2.2 On Assignments and $l$-Assignments

We will now present the notions of assignments and $l$-assignments we will
then move on to define list agreement expanders.

We will start by defining assignments and agreeing assignments. Assignments
are essentially a set of local functions from every $k$-dimensional face of
the complex to $\left\\{0,1\right\\}$, while agreeing assignments can be
thought of as “snippets” of some global function. We will end the discussion
of assignments by defining the distance between two assignments as the number
of faces on which they differ.

######  Definition 2.18 (Assignment).

Define an assignment to the $k$-faces of a simplicial complex $X$ to be
${\mathcal{{F}}}=\left\\{{\mathcal{{F}}}^{\sigma}\right\\}_{{\sigma}\in X(k)}$
such that ${\mathcal{{F}}}^{\sigma}:{\sigma}\rightarrow\left\\{0,1\right\\}$.
We also denote the set of assignments by $\boldsymbol{{\mathcal{{S}}}}$.

######  Definition 2.19 (Agreeing assignment).

Define the set of agreeing assignments to the $k$-faces to be:

$\boldsymbol{{\mathcal{{A}}}}=\left\\{{\mathcal{{F}}}\middle|\exists{F}\in
C^{0}\left(X\right)\forall{\sigma}\in
X(k):{F}|_{\sigma}={\mathcal{{F}}}^{\sigma}\right\\}$

We also say that ${\mathcal{{F}}}$ agrees with ${F}$.

######  Definition 2.20 (Distance function for assignments).

Define the distance between two
$k$-assignments as:

$\operatorname{dist}{({\mathcal{{F}}},{\mathcal{{G}}})}=\left\|\left\\{{\sigma}\in
X(k)\middle|{\mathcal{{F}}}^{\sigma}\neq{\mathcal{{G}}}^{\sigma}\right\\}\right\|$

In addition, given a set of assignments $\boldsymbol{{\mathcal{{S}}}}$ define
the distance of an assignment ${\mathcal{{F}}}$ from
$\boldsymbol{{\mathcal{{S}}}}$ to be:

$\operatorname{dist}{\left({\mathcal{{F}}},\boldsymbol{{\mathcal{{S}}}}\right)}=\min_{{\mathcal{{S}}}\in\boldsymbol{{\mathcal{{S}}}}}{\left\\{\operatorname{dist}{({\mathcal{{F}}},{\mathcal{{S}}})}\right\\}}$

We are now ready to define $l$-assignments and agreeing $l$-assignments.
$l$-assignments are $l$ parallel assignments, i.e. every face in the complex
has $l$ local functions associated with it.

######  Definition 2.21 ($l$-assignments).

Given a simplicial complex $X$ define a $k$-dimensional $l$-assignment to be:

${\mathscr{{F}}}=\left\\{{\mathscr{{F}}}^{\sigma}_{i}\right\\}_{{\sigma}\in
X(k),i\in[l]}$

Such that:

${\mathscr{{F}}}^{\sigma}_{i}:{\sigma}\rightarrow\left\\{0,1\right\\}$

An assignment of $l$ local function to each $k$-face of $X$.

We define the distance between two $l$-assignments as the number of local
functions on which they differ (normalised by the weights of the faces and the
length of the list).

######  Definition 2.22 (Distance between $l$-assignments).

Define the distance between two $k$-dimensional $l$-assignments as:

$\operatorname{dist}{({\mathscr{{F}}},{\mathscr{{G}}})}=\sum_{{\sigma}\in
X(k)}{\operatorname{w}\left({\sigma}\right)\frac{\left|\left\\{i\in[l]\middle|{\mathscr{{F}}}_{i}^{\sigma}\neq{\mathscr{{G}}}_{i}^{\sigma}\right\\}\right|}{l}}$

In addition, given a set of $l$-assignments ${\boldsymbol{{\mathscr{{S}}}}}$
define the distance of an $l$-assignment ${\mathscr{{F}}}$ from
${\boldsymbol{{\mathscr{{S}}}}}$ to be:

$\operatorname{dist}{\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{S}}}}}\right)}=\min_{{\mathscr{{S}}}\in{\boldsymbol{{\mathscr{{S}}}}}}{\left\\{\operatorname{dist}{({\mathscr{{F}}},{\mathscr{{S}}})}\right\\}}$

The notion of agreement in this case is more complicated then in the non-list
case. In regular assignments an agreeing assignment is an assignment that is
consistent with some global function. In the $l$-assignment agreement case we
are interested whether there are $l$ global functions such that the local
assignments of each vertex are a list of “snippets” of the $l$ global
functions.

######  Definition 2.23 (Agreeing $l$-assignment).

Define an agreeing $k$-dimensional $l$-assignments to be a $k$-dimensional
$l$-assignment ${\mathscr{{F}}}$ such that there are $l$ cochains
${F}_{1},\dots,{F}_{l}\in C^{0}\left(X\right)$ and for every face ${\sigma}\in
X(k)$ there exists a permutation $\pi_{\sigma}$ such that the assignment
${\mathcal{{F}}}_{i}=\left\\{{\mathscr{{F}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}_{{\sigma}\in
X(k)}$ agrees with ${F}_{i}$. Denote the set of agreeing assignments as
${\boldsymbol{{\mathscr{{A}}}}}$.

We are now ready to define list agreement expansion:

######  Definition 2.24 (List agreement expander).

Let $X$ be a $d$-dimensional pure simplical complex. We say that $X$ is a
$(\beta,l)$-agreement-expander if there is a probabilistic algorithm $A$ such
that for every dimension $k$ and every $k$-dimensional $l$-assignment
${\mathscr{{F}}}$ it holds that:

$\frac{\Pr\left[A^{\mathscr{{F}}}\text{
rejects}\right]}{\operatorname{dist}\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}}\right)}\geq\beta$

In this paper we will present a weaker notion of list agreement expander.
Specifically we are going to assume that the $l$-assignments are $2$-locally-
different defined below:

######  Definition 2.25 (Locally differing $l$-assignment).

Let ${\mathscr{{F}}}$ be an $l$-assignment. We say that ${\mathscr{{F}}}$ is
$2$-locally-differing if for every $i\neq j$, every ${\sigma}\in X(k)$ there
exists $x^{{\sigma},i,j}_{1}\neq x^{{\sigma},i,j}_{2}$ such that:

${\mathscr{{F}}}^{{\sigma}}_{i}(x^{{\sigma},i,j}_{1})\neq{\mathscr{{F}}}^{{\sigma}}_{j}(x^{{\sigma},i,j}_{1})\text{
and
}{\mathscr{{F}}}^{{\sigma}}_{i}(x^{{\sigma},i,j}_{2})\neq{\mathscr{{F}}}^{{\sigma}}_{j}(x^{{\sigma},i,j}_{2})$

Before we conclude this section it will be helpful to consider the following
property of the distance between an $l$-assignment and the agreeing
$l$-assignments:

######  Lemma 2.26.

For every set of permutations $\left\\{\pi_{\sigma}\right\\}_{{\sigma}\in
X(k)}$ it holds that:

$\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}\leq\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}\left(\left\\{{\mathscr{{F}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}_{{\sigma}\in
X(k)},\boldsymbol{{\mathcal{{A}}}}\right)}$

###### Proof.

Let $\left\\{\pi_{\sigma}\right\\}_{{\sigma}\in X(k)}$ be a set of
permutations. Consider the assignments
${\mathcal{{F}}}_{i}=\left\\{{\mathscr{{F}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}_{{\sigma}\in
X(k)}$. For every ${\mathcal{{F}}}_{i}$ let ${\mathcal{{G}}}_{i}$ be an
agreeing $k$-assignment such that
$\operatorname{dist}\left({\mathcal{{F}}}_{i},{\mathcal{{G}}}_{i}\right)=\operatorname{dist}\left({\mathcal{{F}}}_{i},\boldsymbol{{\mathcal{{A}}}}\right)$.
Consider the $l$-assignment
${\mathscr{{G}}}=\left\\{{\mathscr{{G}}}^{\sigma}_{i}\right\\}_{{\sigma}\in
X(k)}$ such that
${\mathscr{{G}}}^{\sigma}_{i}={\mathcal{{G}}}_{\pi_{\sigma}^{-1}(i)}^{\sigma}$.
Note that ${\mathscr{{G}}}$ is an agreeing $k$-dimensional $l$-assignment
since $\left\\{{\mathscr{{G}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}$ is an
agreeing $k$-dimensional assignment for all $i$. We finish the proof by noting
that:

$\displaystyle\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}$
$\displaystyle\leq\operatorname{dist}{({\mathscr{{F}}},{\mathscr{{G}}})}=\sum_{{\sigma}\in
X(k)}{w({\sigma})\frac{\left|\left\\{i\in[l]\middle|{\mathscr{{F}}}_{i}^{\sigma}\neq{\mathscr{{G}}}_{i}^{\sigma}\right\\}\right|}{l}}$
$\displaystyle=\frac{1}{l}\sum_{{\sigma}\in
X(k)}{w({\sigma})\left|\left\\{i\in[l]\middle|{\mathscr{{F}}}_{\pi_{\sigma}(i)}^{\sigma}\neq{\mathscr{{G}}}_{\pi_{\sigma}(i)}^{\sigma}\right\\}\right|}$
$\displaystyle=\frac{1}{l}\sum_{{\sigma}\in
X(k)}{w({\sigma})\sum_{i=1}^{l}{\mathbbm{1}_{\left\\{{\mathscr{{F}}}_{\pi_{\sigma}(i)}^{\sigma}\neq{\mathscr{{G}}}_{\pi_{\sigma}(i)}^{\sigma}\right\\}}(i,{\sigma})}}$
$\displaystyle=\frac{1}{l}\sum_{i=1}^{l}{\sum_{{\sigma}\in
X(k)}{w({\sigma})\mathbbm{1}_{\left\\{{\mathscr{{F}}}_{\pi_{\sigma}(i)}^{\sigma}\neq{\mathscr{{G}}}_{\pi_{\sigma}(i)}^{\sigma}\right\\}}(i,{\sigma})}}$
$\displaystyle=\frac{1}{l}\sum_{i=1}^{l}{\sum_{{\sigma}\in\left\\{{\tau}\in
X(k)\middle|{\mathscr{{F}}}_{\pi_{\tau}(i)}^{\tau}\neq{\mathscr{{G}}}_{\pi_{\tau}(i)}^{\tau}\right\\}}{w({\sigma})}}$
$\displaystyle=\frac{1}{l}\sum_{i=1}^{l}{\left\|\left\\{{\sigma}\in
X(k)\middle|{\mathscr{{F}}}_{\pi_{\sigma}(i)}^{\sigma}\neq{\mathscr{{G}}}_{\pi_{\sigma}(i)}^{\sigma}\right\\}\right\|}$
$\displaystyle=\frac{1}{l}\sum_{i=1}^{l}{\left\|\left\\{{\sigma}\in
X(k)\middle|{\mathcal{{F}}}_{i}^{\sigma}\neq{\mathcal{{G}}}_{i}^{\sigma}\right\\}\right\|}=\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}\left({\mathcal{{F}}}_{i},{\mathcal{{G}}}_{i}\right)}=\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}\left({\mathcal{{F}}}_{i},\boldsymbol{{\mathcal{{A}}}}\right)}$

∎

######  Corollary 2.27.

Let ${\mathscr{{F}}}$ be an $l$-assignment and let $\tilde{{\mathscr{{F}}}}$
be an agreeing $l$-assignment such that
$\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}=\operatorname{dist}{({\mathscr{{F}}},\tilde{{\mathscr{{F}}}})}$.
In addition let $\left\\{\pi_{\sigma}\right\\}_{{\sigma}\in X(k)}$ be a
permutation such that for every $i$:
$\left\\{\tilde{{\mathscr{{F}}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}_{{\sigma}\in
X}$ is an agreeing assignment then:

$\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}=\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}\left(\left\\{{\mathscr{{F}}}^{\sigma}_{\pi_{\sigma}(i)}\right\\}_{{\sigma}\in
X(k)},\boldsymbol{{\mathcal{{A}}}}\right)}$

###### Proof.

Define ${\mathscr{{G}}}$ as in Lemma 2.26 and note that
${\mathscr{{G}}}=\tilde{{\mathscr{{F}}}}$. Also note that
$\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}=\operatorname{dist}{({\mathscr{{F}}},\tilde{{\mathscr{{F}}}})}=\operatorname{dist}{({\mathscr{{F}}},{\mathscr{{G}}})}$.
From here the proof follows the proof of Lemma 2.26. ∎

###  2.3 Coboundary Expansion

The first form of high dimensional expansion we will present is _coboundary
expansion_. Coboundary expansion was first defined by Linial and Meshulam
[LM06] and independently by Gomov [Gro10]. This form of expansion generalizes
the notion of $1$-dimensional expansion naturally. Before we define the
coboundary expansion to higher dimensions, we will re-define the
$0$-dimensional expansion in the language that will allow for easier
generalization. Consider the standard definition of Cheeger’s constant:

######  Definition 2.28 (Cheeger’s constant).

Let $X=(X,E)$ be a graph, define the Cheeger constant of a graph to be:

$\min_{A\neq V,\emptyset}{\left\\{\frac{\left|E(A,V\setminus
A)\right|}{\min{\left|A\right|,\left|V\setminus A\right|}}\right\\}}$

In our redefinition, instead of subsets of the vertices we will consider
$0$-dimensional cochains with coefficients in $\mathbbm{F}_{2}$. We will
represent a set of vertices $A\subseteq V$ be the following cochain:

${F}_{A}({v})=\begin{cases}1&{v}\in A\\\ 0&{v}\notin A\end{cases}$

Consider how, in our new setting, we can describe an edge between $A$ and
$\bar{A}$ and note that the set of edges $\left\\{{v},{u}\right\\}$ that are
between $A$ and $\bar{A}$ are exactly the edges for which
$d_{0}{F}_{A}({v},{u})\neq 0$. Lastly, consider the following reformulation of
the Cheeger’s constant:

$\min_{{F}\in C^{0}\left(X\right)\setminus
B^{0}\left(X\right)}{\left\\{\frac{\left\|d_{0}{F}\right\|}{\operatorname{dist}\left({F},B^{0}\left(X\right)\right)}\right\\}}$

Note that $B^{0}\left(X\right)$ contains the cochains that correspond to $V$
and $\emptyset$. Now, consider the following generalization of that
reformulation of Cheeger’s constant:

######  Definition 2.29 ($i$-dimensional expansion).

Define the $i$th dimensional Cheeger constant to be:

$h_{i}(X;G)=\min_{{F}\in C^{i}\left(X;G\right)\setminus
B^{i}\left(X;G\right)}{\left\\{\frac{\left\|d_{i}{F}\right\|}{\operatorname{dist}\left({F},B^{i}\left(X;G\right)\right)}\right\\}}$

If $h_{i}(X;G)\geq\epsilon$ we say that the $i$th dimension of $X$
$\epsilon$-expands with $G$-coefficients.

And the following generalization of expansion:

######  Definition 2.30 (Coboundary expansion).

Let $X$ be a $d$-dimensional simplicial complex. We say that $X$ is an
$\epsilon$-coboundary expander with coefficients in $G$ if for every face
${\sigma}\in X$ with dimension smaller than $d-2$ it holds that
$h_{0}(X_{\sigma};G)\geq\epsilon$ and $h_{1}(X_{\sigma};G)\geq\epsilon$.

In [KM21] Kaufman and Mass showed how to construct coboundary expanders
independently of the underlying group.

###  2.4 Covers of Simplicial Complexes

We will now move on to formally present the concept of covers of simplicial
complexes and their connection to the cocycles of the simplicial complex:

######  Definition 2.31 (Cover space).

Let $X,{Y}$ be two $d$-dimensional simplicial complexes. We say that
$\left({Y},f_{Y}\right)$ $l$-fold evenly covers $X$ if $f_{Y}$ is a surjective
map from ${Y}$ to $X$ such that:

  * •

$f_{Y}$ is a translation function: for every ${\sigma}\in{Y}$ it holds that
$\left|{\sigma}\right|=\left|f_{Y}{({\sigma})}\right|$ and
${\sigma}\subseteq{\tau}\Leftrightarrow f_{Y}({\sigma})\subseteq
f_{Y}({\tau})$

  * •

Locally $X$ and ${Y}$ look the same: for every face ${\sigma}\in{Y}$, $f_{Y}$
is an isomorphism between
$\left\\{{\tau}\in{Y}\middle|{\sigma}\subseteq{\tau}\right\\}$ and
$\left\\{{\tau}\in X\middle|f_{Y}({\sigma})\subseteq{\tau}\right\\}$.

  * •

Every non-empty face of $X$ is covered by exactly $l$-faces from ${Y}$:
$\forall{\sigma}\in
X\setminus\left\\{\emptyset\right\\}:\left|f_{Y}^{-1}({\sigma})\right|=l$

We will refer to $f_{Y}$ as the covering map from ${Y}$ to $X$. In addition we
are going to say that ${Y}$ is an $l$-cover of $X$ if there exists a covering
map from ${Y}$ to $X$. Lastly we would sometimes refer to a cover as defined
here as a _genuine_ cover (as opposed to a near cover, defined below).

######  Definition 2.32 (Lift).

Let $X$ be a simplicial complex, ${Y}$ be a cover of $X$ with the covering map
$f_{Y}$. Also let $\gamma=\left(\gamma_{1},\cdots,\gamma_{n}\right)$ be a path
in $X$. A lift of $\gamma$ to ${Y}$ is a path
$\gamma^{\prime}=\left(\gamma_{1}^{\prime},\cdots,\gamma_{n}^{\prime}\right)$
in ${Y}$ such that for all $i$ it holds that
$f_{Y}(\gamma_{i}^{\prime})=\gamma_{i}$.

We also adopt the definition of near covers defined by [DM19]:

######  Definition 2.33 (Near cover).

Let $X$ be a simplicial complex and let ${Y}$ be another simplicial complex.
We say that ${Y}$ is an $l$ near cover of $X$ if there exists a function
$f_{Y}:{Y}\rightarrow X$ such that:

  * •

For each vertex ${v}\in X(0)$ it holds that $f_{Y}^{-1}$ can be identified
with $\left[l\right]$. We will therefore use the notation $\left[u,i\right]$
to denote the vertex in $f_{Y}^{-1}\left[{u}\right]$ that corresponds to $i$.

  * •

For every edge $({v},{u})\in X(1)$ there exists $\pi\in S_{l}$ such that if
$f_{Y}(\left[{v},i\right],\left[{u},j\right])=({v},{u})$ then
$i=\pi\left(j\right)$.

Where $S_{l}$ is the symmetric group of order $l$.

Note that the difference between near covers and genuine covers is that in
near covers the faces of dimension larger or equal to $2$ might not be
properly covered. Consider, for example, a complex that contains a single
triangle $T=\left\\{\left\\{{v}_{1},{v}_{2},{v}_{3}\right\\}\right\\}$ and
consider the near cover of $T$ whose $1$-dimensional faces are (where
$G=\mathbbm{F}_{2}$):

${Y}(1)=\left\\{\begin{subarray}{c}\left\\{[{v}_{1},0],[{v}_{2},0]\right\\},\left\\{[{v}_{2},0],[{v}_{3},1]\right\\},\left\\{[{v}_{3},1],[{v}_{1},1]\right\\},\\\
\left\\{[{v}_{1},1],[{v}_{2},1]\right\\},\left\\{[{v}_{2},1],[{v}_{3},0]\right\\},\left\\{[{v}_{3},0],[{v}_{1},0]\right\\}\end{subarray}\right\\}$

Note that it is indeed a near cover since every vertex ${v}_{i}$ is covered by
$[{v}_{1},0],[{v}_{1},1]$ which can be identified with $0$ and $1$
respectively. In addition, since $\mathbbm{F}_{2}$ is the symmetric group the
second condition holds trivially. Also note that ${Y}$ is not a cover of ${T}$
since the second and third conditions of being a cover fail: The first
condition fails for any vertex in the complex (since every vertex is a member
of the triangle therefore $\left\\{{\tau}\in
X\middle|f_{Y}({\sigma})\subseteq{\tau}\right\\}$ contains a set of size 3
while $\left\\{{\tau}\in{Y}\middle|{\sigma}\subseteq{\tau}\right\\}$ contains
no such sets121212${Y}$’s $1$-dimensional faces form a cycle of length 6 and
therefore no triangle can be formed using the edges of ${Y}$.). Let us now
note that every $1$-dimensional cochain in $X$ implies a near cover by the
following:

######  Definition 2.34.

Let $G$ be a group acting on the left of a set $S$ and let ${F}\in
C^{1}\left(X;G\right)$. Define the complex ${Y}_{F}$ as the complex whose
$0$-dimensional faces are ${Y}_{F}(0)=\left\\{[{v},s]\middle|{v}\in X\text{
and }s\in S\right\\}$ and its higher dimensional faces are:

${Y}_{F}(i)=\left\\{\left\\{[{v}_{0},s_{0}],\dots[{v}_{i},s_{i}]\right\\}\middle|\left\\{{v}_{0},\dots,{v}_{i}\right\\}\in
X\text{ and }\forall i,j:s_{i}={F}({v}_{i},{v}_{j})s_{j}\right\\}$

Surowski showed in [Sur84, Proposition 3.2] a characterization of when
${Y}_{F}$ is a genuine cover of $X$. Specifically:

######  Lemma 2.35 (Proposition 3.2 in [Sur84], rephrased).

${Y}_{F}$ is a genuine cover of $X$ with the covering map
$f_{{Y}_{F}}(\left\\{[{v}_{0},s_{0}],\dots[{v}_{i},s_{i}]\right\\})=\left\\{{v}_{0},\dots,{v}_{i}\right\\}$
iff ${F}$ is a cocycle.

###  2.5 Agreement Expansion

Another type of high dimensional expansion is agreement expansion. This type
of expansion is concerned with the relation between agreement of local
assignments and the distance of an assignment from agreeing. It was first
introduced by Dinur and Kaufman in [DK17]. In this subsection we will
introduce the concept of agreement testing which is a crucial part of our
construction:

######  Definition 2.36 (Agreement expansion in the $i$-th dimension).

Let $X$ be a $d$-dimensional simplicial complex and let $\mathcal{D}$ be a
distribution over pairs of $i$ dimensional faces that intersect each other on
$\xi$ vertices131313$p$ may be dependent on $i$.. Define:

$a_{i,\xi}(X,\mathcal{D})=\min_{{\mathcal{{A}}}\in\boldsymbol{{\mathcal{{S}}}}}{\left\\{\frac{\Pr_{({\sigma},{\tau})\sim\mathcal{D}}\left[{\mathcal{{A}}}^{\sigma}|_{{\sigma}\cap{\tau}}={\mathcal{{A}}}^{\tau}|_{{\sigma}\cap{\tau}}\right]}{\operatorname{dist}{\left({\mathcal{{A}}},\boldsymbol{{\mathcal{{A}}}}\right)}}\right\\}}$

In addition let us define an agreement expander:

######  Definition 2.37 (Agreement expander).

Let $X$ be a $d$-dimensional simplicial complex and let $\mathcal{D}$ be a
distribution. We say that $X$ is an $\alpha$-agreement-expander if:

$\forall 0\leq i\leq
d:a_{i,\xi}(X,\mathcal{D})\geq\alpha\left(1-\frac{\xi}{i}\right)$

Note that the dependency on the $\left(1-\frac{i}{\xi}\right)$ stems from the
second eigenvalue of the random walk that walks between two $i$ dimensional
faces via a $i+\xi$ dimensional face.

In this paper we will be interested in a special case of agreement expander,
specifically $1$-up agreement expander.

######  Definition 2.38 ($1$-up agreement expander).

Define the distribution $\mathcal{D}_{\uparrow}$ as the distribution that, in
order to sample two $i$-dimensional faces, samples an $(i+1)$-dimensional face
and then sample two of its $i$-dimensional sub-faces. Note that this
distribution guarantees an intersection of size $i-1$. We say that a
simplicial complex is a $1$-up agreement expansion if it is an agreement
expander with the distribution $\mathcal{D}_{\uparrow}$.

##  3 The Representation Complex

In this section we are going to present a new complex that represents the
agreement test over the complex we are interested in. We will do that by
constructing an edge for each of the possible choices of the 1-up agreement
test. We will add higher dimensional faces so that the norm of the faces in
the representation complex would correspond with the weight of the faces they
represent. Then we will analyze the structure of this new complex. We finish
the discussion of the representation complex by discussing its expansion
properties.

######  Definition 3.1 (Representation Function).

Define the representation function of a set of $k$-faces to be
$R:P(X(k))\rightarrow P(X(0))$ to be $R(s)=\bigcup_{s^{\prime}\in
s}{s^{\prime}}$.

######  Definition 3.2 (Representation Complex).

Given a simplicial complex $X$ define the representation complex of $X$ to be
$\hat{R}^{k}(X)$ such that:

  * •

$\hat{R}^{k}(X)(-1)=\left\\{\emptyset\right\\}$

  * •

$\hat{R}^{k}(X)(0)=\left\\{\left\\{{\sigma}\right\\}\middle|{\sigma}\in
X(k)\right\\}$

  * •

$\forall 1\leq i\leq
d-k:\hat{R}^{k}(X)(i)=\left\\{{\sigma}\in\binom{X(k)}{i+1}\middle|R({\sigma})\in
X(i+k)\text{ and }\left|\bigcap_{{v}\in{\sigma}}{{v}}\right|=k\right\\}$

######  Note.

For clarity of notation we will treat $\hat{R}^{k}(X)(0)$ as if it equals
$X(k)$ (i.e. we will consider $\left\\{{\sigma}\right\\}$ and ${\sigma}$ to be
equivalent when discussing the representation complex’s $0$-dimensional
faces). Moreover, we will sometimes treat $R$ as a function whose origin is
the faces in $\hat{R}^{k}(X)$ (which are subsets of $X(k)$) and range is the
faces of $X$.

######  Definition 3.3.

We say that a face ${\sigma}\in X$ is represented by
$r_{\sigma}\in\hat{R}^{k}(X)$ if $R(r_{\sigma})={\sigma}$. Conversely we say
that $r_{\sigma}$ represents ${\sigma}$.

Now that we have defined the notion of representation in the new structure it
is time to start analyzing it. We will show that every face whose dimension is
larger then $1$ has sunflower-like structure i.e. there is a core that is a
subset of each of the vertices in the face. And, in addition, the core is the
intersection of any two vertices in the face.

######  Definition 3.4.

Define the core of a face ${\sigma}\in\hat{R}^{k}(X)$ to be:
$core\left({\sigma}\right)=\bigcap_{{v}\in{\sigma}}{{v}}$

######  Lemma 3.5.

Let $d\geq 1$ and let ${\sigma}\in\hat{R}(X(d))$, then every
${v}_{1},{v}_{2}\in{\sigma}$ such that ${v}_{1}\neq{v}_{2}$ it holds that:
${v}_{1}\cap{v}_{2}=core\left({\sigma}\right)$

###### Proof.

Using the counter positive argument assume that there exists ${v}_{1},{v}_{2}$
such that ${v}_{1}\cap{v}_{2}\neq core\left({\sigma}\right)$. Since
$\left|\bigcap_{{v}\in{\sigma}}{{v}}\right|=k$ we know that
${v}_{1}\cap{v}_{2}\supseteq\bigcap_{{v}\in{\sigma}}{{v}}=core\left({\sigma}\right)$.
We also know that $\left|{v}_{1}\right|=\left|{v}_{2}\right|=k+1$ therefore if
$\left|{v}_{1}\cap{v}_{2}\right|=k+1$ then ${v}_{1}={v}_{2}$ which contradicts
our assumption. In the case where $\left|{v}_{1}\cap{v}_{2}\right|=k$ it holds
that $\left|{v}_{1}\cap{v}_{2}\right|=\left|core\left({\sigma}\right)\right|$
which proves the lemma. ∎

We can now prove that the representation complex is indeed a simplicial
complex:

######  Lemma 3.6 (The representation complex is a simplicial complex).

The representation complex is a simplicial complex.

###### Proof.

Let ${\sigma}\in\hat{R}^{k}(X)$ be a face and let $\tilde{{\sigma}}$ be a
subset of ${\sigma}$. If $\left|\tilde{{\sigma}}\right|=1$ then
$\tilde{{\sigma}}$ is exactly one of the vertices and therefore in
$\hat{R}^{k}(X)$. In any other case $R(\tilde{{\sigma}})\subseteq
R({\sigma})\in X$ and therefore $R(\tilde{{\sigma}})\in X$. In addition it is
easy to see that due to Lemma 3.5 it holds that
$\left|\bigcap_{{\tau}\in{\sigma}}{{\tau}}\right|=k$. Therefore
$\bar{{\sigma}}\in\hat{R}^{k}(X)$ and the representation complex is a
simplicial complex. ∎

###  3.1 On the Structure of the Representation Complex

We will now discuss the structure of the representation complex including how
it represents the original complex. We will begin by considering how each face
is represented in the representation complex. Specifically we will show that
every face is represented in the representation complex once for every one of
its cores (which are the $\left(k-1\right)$-faces contained in it).

######  Lemma 3.7.

Let ${\sigma}$ be a face in $X(k+i)$ (such that $i\geq 1$). And let
$c\in\binom{{\sigma}}{k}$ be a possible core of ${\sigma}$ (i.e. a
$(k-1)$-dimensional sub-face of ${\sigma}$). Then there exists a single face
$r^{c}_{{\sigma}}$ such that ${\sigma}$ is represented by $r^{c}_{{\sigma}}$
and $core\left(r^{c}_{{\sigma}}\right)=c$.

###### Proof.

Consider
$r^{c}_{{\sigma}}=\left\\{c\cup\left\\{{v}\right\\}\middle|{v}\in{\sigma}\setminus
c\right\\}$. We will start by proving that this is indeed a face in the
representation complex:

  * •

$c\cup\left\\{{v}\right\\}\subseteq{\sigma}$ and, in addition,
$\left|c\cup\left\\{{v}\right\\}\right|=k+i+1$ therefore
$c\cup\left\\{{v}\right\\}\in X(k)$.

  * •

$\left|r^{c}_{{\sigma}}\right|=\left|{\sigma}\setminus c\right|=i+1$.

  * •

It is easy to see that $R(r^{c}_{{\sigma}})={\sigma}\in X(k+i)$.

  * •

$\left|\bigcap_{{v}\in{\sigma}}{{v}}\right|=\left|c\right|=k$.

Therefore $r^{c}_{{\sigma}}$ is a face in the representation complex which
represents ${\sigma}$. We will use the counter-positive argument in order to
prove that $r^{c}_{{\sigma}}$ is singular up to the core $c$. Assume that
there are two different faces
$\tilde{r^{c}_{{\sigma}}},\hat{r^{c}_{{\sigma}}}$ that represent ${\sigma}$
and have the same core $c$. WLOG assume that
$\tilde{r^{c}_{{\sigma}}}{\displaystyle\not\subseteq}\hat{r^{c}_{{\sigma}}}$
and let ${\tau}\in\hat{r^{c}_{{\sigma}}}\setminus\tilde{r^{c}_{{\sigma}}}$.
Let ${v}$ be the vertex such that ${v}\in{\tau}\setminus c$. Because
$\tilde{r^{c}_{{\sigma}}}$ and $\hat{r^{c}_{{\sigma}}}$ represent the same
face there must be some ${\tau}^{\prime}\in\tilde{r^{c}_{{\sigma}}}$ such that
${v}\in{\tau}^{\prime}$. Since ${v}\notin c$ the only candidate for
${\tau}^{\prime}$ is $c\cup\left\\{{v}\right\\}$ (since
$\left|{\tau}^{\prime}\right|$ must be $k+1$). Therefore
${\tau}={\tau}^{\prime}\in\tilde{r^{c}_{{\sigma}}}$ which contradicts our
assumption on ${\tau}$. ∎

######  Notation 3.8.

Denote by $r^{k,c}_{{\sigma}}$ the face in the representation complex of the
$k$-dimensional faces whose core is $c$ and represents ${\sigma}$. In most
cases the dimension will be clear from context we would omit the dimension
from the notation and denote the face by $r^{c}_{{\sigma}}$.

The following three corollaries follow directly from the characterization of
the representation of a $k$-dimensional face:

######  Corollary 3.9.

$R^{-1}({\sigma})=\left\\{r^{c}_{{\sigma}}\middle|c\in\binom{{\sigma}}{k}\right\\}$

######  Corollary 3.10.

For every face ${\sigma}\in X(k+i)$ ($i>0$) and every two different possible
cores $c_{1},c_{2}\in\binom{{\sigma}}{k}$ such that $c_{1}\neq c_{2}$ it holds
that $r^{c_{1}}_{{\sigma}}\neq r^{c_{2}}_{{\sigma}}$

###### Proof.

Assuming that $r^{c_{1}}_{{\sigma}}=r^{c_{2}}_{{\sigma}}$, then for every face
in ${\tau}\in r^{c_{1}}_{{\sigma}}$ it holds that $c_{1}\cup
c_{2}\subseteq{\tau}$ which contradicts the fact that the cardinality of the
core is exactly $k$. ∎

######  Corollary 3.11.

For every ${i}>0$ and every face ${\sigma}\in X(k+i)$:

$\left|R^{-1}({\sigma})\right|=\begin{cases}\binom{k+i+1}{k}&i>0\\\
1&i=0\end{cases}$

Now that we understand the representation better we move on to discuss the
norm of the representation complex. Although we discuss the norm in every
dimension of the representation complex, the $1$-dimensional faces of the
representation complex are of particular interest. Specifically we will show
that sampling a $1$-dimensional face in the representation complex (with the
appropriate norm) is equivalent to the choice that the 1-up agreement test
preforms. We will start the discussion by showing how the weight function in
the representation complex relates to the weight function of the original
complex:

######  Lemma 3.12.

For every face ${\sigma}\in X(k+i)$ and every representation of the face
$r^{c}_{{\sigma}}$ it holds that:

$\operatorname{w}_{{\hat{R}^{k}(X)}}\left(r^{c}_{{\sigma}}\right)=\frac{1}{\left|R^{-1}({\sigma})\right|}\operatorname{w}_{X}\left({\sigma}\right)$

###### Proof.

For $i>0$:

$\displaystyle\operatorname{w}_{\hat{R}^{k}(X)}\left(r^{c}_{{\sigma}}\right)$
$\displaystyle=\frac{\left|\left\\{{\tau}\in\hat{R}^{k}(X)(d-k)\middle|r^{c}_{{\sigma}}\subseteq{\tau}\right\\}\right|}{\binom{d-k+1}{i+1}\cdot\left|\hat{R}^{k}(X)(d-k)\right|}=\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{d-k+1}{i+1}\binom{d+1}{k}\left|X(d)\right|}=$
$\displaystyle=\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{k+i+1}{k}\binom{d+1}{k+i+1}\left|X(d)\right|}=\frac{1}{\binom{k+i+1}{k}}\cdot\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{d+1}{k+i+1}\left|X(d)\right|}=$
$\displaystyle=\frac{1}{\binom{k+i+1}{k}}\cdot\operatorname{w}_{X}\left({\sigma}\right)=\frac{1}{\left|R^{-1}({\sigma})\right|}\operatorname{w}_{X}\left({\sigma}\right)$

The second equality is due to the fact that every maximal face in the original
complex is represented by $\binom{d+1}{k}$ faces in the representation
complex. In addition, the third equality is due to Lemma C.1. For $i=0$:

$\displaystyle\operatorname{w}_{\hat{R}^{k}(X)}\left(r^{c}_{{\sigma}}\right)$
$\displaystyle=\frac{\left|\left\\{{\tau}\in\hat{R}^{k}(X)(d-k)\middle|r^{c}_{{\sigma}}\subseteq{\tau}\right\\}\right|}{\binom{d-k+1}{1}\cdot\left|\hat{R}^{k}(X)(d-k)\right|}=\frac{\binom{k+1}{k}\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{d-k+1}{1}\binom{d+1}{k}\left|X(d)\right|}=$
$\displaystyle=\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\left(\frac{d-k+1}{k+1}\binom{d+1}{k}\right)\left|X(d)\right|}=$
$\displaystyle=\frac{\left|\left\\{{\tau}\in
X(d)\middle|{\sigma}\subseteq{\tau}\right\\}\right|}{\binom{d+1}{k+1}\left|X(d)\right|}=\operatorname{w}_{X}\left({\sigma}\right)=\frac{1}{\left|R^{-1}({\sigma})\right|}\operatorname{w}_{X}\left({\sigma}\right)$

The second equality holds because the representation of a $k$-dimensional face
${\sigma}$ is contained in the representation of any face in
$\operatorname{\Gamma}\left({\sigma}\right)$. Therefore if ${\sigma}$ is
contained in some maximal face ${\tau}$ then $r^{c}_{{\sigma}}$ is contained
in the $\binom{k+1}{k}$ representations of ${\tau}$ whose cores lie in
${\sigma}$. ∎

######  Corollary 3.13.

$\left\|R^{-1}({\sigma})\right\|=\left\|\left\\{{\sigma}\right\\}\right\|$

Now let us consider how one can sample a face (of any dimension) in the
representation complex with probability relative to its weight. Consider the
following algorithm:

1 Sample ${\tau}\in X(k+i)$ according to the norm of $X$.

2 Pick a set $c\in\binom{{\tau}}{k}$ uniformly at random.

Return $r^{c}_{\tau}$

Algorithm 1 sample from the representation complex

######  Lemma 3.14.

One can sample from the representation complex according to its norm.

###### Proof.

We will show that Algorithm 1 samples faces of dimension $i$ according to
their weight. Let $r^{c^{\prime}}_{{\sigma}}$ be a face of dimension $i\geq 1$
in the representation complex. Then:

$\displaystyle\Pr\left[\text{Algorithm~{}\ref{alg:sample-from-the-
representation-complex} outputs }r^{c}_{{\sigma}}\right]$
$\displaystyle=\Pr\left[{\tau}={\sigma}\wedge
c=c^{\prime}\right]=\Pr\left[{\tau}={\sigma}\wedge
c=c^{\prime}\middle|{\tau}={\sigma}\right]\Pr\left[{\tau}={\sigma}\right]$
$\displaystyle=\Pr\left[c=c^{\prime}\middle|{\tau}={\sigma}\right]\Pr\left[{\tau}={\sigma}\right]=\frac{1}{\binom{k+i+1}{k}}\operatorname{w}_{X}\left({\sigma}\right)=\frac{1}{\left|R^{-1}({\sigma})\right|}\operatorname{w}_{X}\left({\sigma}\right)$
$\displaystyle=\operatorname{w}_{\hat{R}^{k}(X)}\left(r^{c}_{{\sigma}}\right)$

The first equality is due to Lemma 3.7 and the last equality is due to Lemma
3.12.
If $r^{c^{\prime}}_{{\sigma}}$ is a face of dimension $0$ then step 1 can be
ignored since the representation for these faces is independent of the core
chosen and the algorithm outputs $\tau$. ∎

Consider now what happens when Algorithm 1 samples a $1$-dimensional face in
the representation complex. It samples a $(k+1)$-dimensional face ${\tau}$ in
the original complex and then chooses a core. Choosing a core is equivalent to
choosing two $k$-dimensional sub-faces of ${\tau}$ (since any core of ${\tau}$
is shared by exactly two faces). Note that this is the exact process in which
the $1$-up agreement test samples its faces. Therefore picking a
$1$-dimensional face in the representation complex corresponds to a choosing
faces in the $1$-up agreement test.

###  3.2 On the Expansion Properties of the Representation Complex

Now that we have defined the representation complex and presented how it
represents the original complex we will move on to discuss the expansion
properties of the representation complex. We will show that the representation
complex, despite not being an expander by itself, does have some expansion
properties. Specifically we are interested in the expansion of the faces of
the first dimension since cocycles in the first dimension correspond with
covers of the complex. In order to discuss the expansion of the representation
complex it will be useful to discuss how faces that share a core behave. Lets
begin by discussing the representation complex around a core:

######  Definition 3.15 (Representation complex around a core).

Define the representation complex of $X$ around a core $c$ to be:

$\hat{R}^{k}_{c}(X)=\left\\{{\sigma}\in\hat{R}^{k}(X)(i)\middle|core\left({\sigma}\right)=c,i\geq
1\right\\}\cup\left\\{{\sigma}\in\hat{R}^{k}(X)(0)\middle|c\subseteq{\sigma}\right\\}\cup\left\\{\emptyset\right\\}$

This is indeed a simplicial complex since it is constructed from picking a set
of faces of maximal dimension from $\hat{R}^{k}(X)$ and all their sub-faces.
We will now prove that around every core the representation complex is a
coboundary expander. We will do that by characterizing them as the
$\left(k-1\right)$-dimensional links of the original complex:

######  Lemma 3.16.

For every core of every face $c\in X(k-1)$ it holds that
$X_{c}\cong\hat{R}^{k}_{c}(X)$.

###### Proof.

Consider the maps $f:\hat{R}^{k}_{c}(X)\rightarrow X_{c}$ and
$g:X_{c}\rightarrow\hat{R}^{k}_{c}(X)$ defined as follows:

$f({\tau})=R({\tau})\setminus c\quad\text{and}\quad
g({\sigma})=r^{c}_{\left({\sigma}\cup c\right)}$

Note that:

$\forall{\tau}\in\hat{R}^{k}_{c}(X):g(f({\tau}))=g(R({\tau})\setminus
c)=r^{c}_{\left(\left(R({\tau})\setminus c\right)\cup
c\right)}=r^{c}_{R({\tau})}={\tau}$ $\forall{\sigma}\in
X_{c}:f(g({\sigma}))=f(r^{c}_{\left({\sigma}\cup c\right)})=\left({\sigma}\cup
c\right)\setminus c={\sigma}$

The last equality in the first line is due to the singular representation of
${\tau}$ per core. The last equality in the second line holds because the core
of all the faces in $\hat{R}^{k}_{c}(X)$ is $c$. In addition:

  * •

If ${\tau}_{1}\subseteq{\tau}_{2}$ then: $f({\tau}_{1})=R({\tau}_{1})\setminus
c=\bigcup_{t\in{\tau}_{1}}{t\setminus
c}\subseteq\bigcup_{t\in{\tau}_{2}}{t\setminus c}=R({\tau}_{2})\setminus
c=f({\tau}_{2})$.

  * •

If ${\sigma}_{1}\subseteq{\sigma}_{2}$ then:
$g({\sigma}_{1})=r^{c}_{\left({\sigma}_{1}\cup
c\right)}=\left\\{\left\\{i\right\\}\cup
c\middle|i\in{\sigma}_{1}\right\\}\subseteq\left\\{\left\\{i\right\\}\cup
c\middle|i\in{\sigma}_{2}\right\\}=r^{c}_{\left({\sigma}_{2}\cup
c\right)}=g({\tau}_{2})$.

∎

######  Note.

In the proof of the previous lemma we disregarded the orientation of the faces
(which we are yet to define for the representation complex). We will define
the orientation of the representation complex to be the orientation that stems
from this isomorphism. It is important to notice that the orientation of the
representation complex is completely determined by the orientation of the
faces in the original complex.

We will continue by showing that the norm of a face in the representation
complex is directly proportional to its weight around each core:

######  Lemma 3.17.

For every core $c$ there exists a constant $t_{c}$ such that for every face
${\sigma}$ whose core is $c$ it holds that
$\operatorname{w}\left({\sigma}\right)_{\hat{R}^{k}(X)}=t_{c}\cdot\operatorname{w}\left({\sigma}\right)_{\hat{R}_{c}(X)}$.

###### Proof.

$\displaystyle\operatorname{w}\left({\sigma}\right)_{\hat{R}^{k}(X)}$
$\displaystyle=\frac{\left|\left\\{{\sigma}^{\prime}\in\hat{R}^{k}(X)(d-k)\middle|{\sigma}\subseteq{\sigma}^{\prime}\right\\}\right|}{\binom{{d-k+1}}{\left|{\sigma}\right|}\left|\hat{R}^{k}(X)(d-k)\right|}$
$\displaystyle=\frac{\left|\hat{R}_{c}(X)(d-k)\right|}{\left|\hat{R}^{k}(X)(d-k)\right|}\cdot\frac{\left|\left\\{{\sigma}^{\prime}\in\hat{R}_{c}(X)(d-k)\middle|{\sigma}\subseteq{\sigma}^{\prime}\right\\}\right|}{\binom{d-k+1}{\left|{\sigma}\right|}\left|\hat{R}_{c}(X)(d-k)\right|}$
$\displaystyle=\frac{\left|\hat{R}_{c}(X)(d-k)\right|}{\left|\hat{R}^{k}(X)(d-k)\right|}\operatorname{w}\left({\sigma}\right)_{\hat{R}_{c}(X)}$

The second equality holds due to Lemma 3.5 ∎

Now that we have characterized the representation complex around each of its
cores it is time to move on to discuss its expansion properties. We will show
how to deconstruct each cochain ${F}$ to a multiplication of other cochains
${F}^{c}$ such that each of the cochains ${F}^{c}$ is restricted, in a sense,
around a core. This deconstruction is going to play a key role in the proof
that the representation complex expands in the first dimension. Specifically,
we know that around every core the complex is an expander and therefore each
of the ${F}^{c}$s expands. This implies that the entire cochain expands. Let
us start be defining the deconstruction:

######  Definition 3.18 (Multiplication of cochains).

Let ${F}_{1},{F}_{2}\in C^{i}\left(X;G\right)$ define the multiplication of
them as:

$({F}_{1}\cdot{F}_{2})({\sigma})={F}_{1}({\sigma})\cdot{F}_{2}({\sigma})$

######  Definition 3.19 (Cochain around a core).

For every dimension $i$ and every cochain
${F}\in C^{i}\left(\hat{R}^{k}(X);G\right)$ define the cochain ${F}$ around
$c$ to be:

${F}^{c}({\sigma})=\begin{cases}{F}({\sigma})&core\left({\sigma}\right)=c\\\
1&\text{otherwise}\end{cases}$

######  Lemma 3.20.

For every cochain ${F}\in C^{i}\left(\hat{R}^{k}(X);G\right)$ ($i\geq 1$) it
holds that:

${F}=\prod_{c\in X(k-1)}{{F}^{c}}$

In addition, for every ${\sigma}\in\hat{R}^{k}(X)(i)$ there exists at most one
core $c$ such that ${F}^{c}({\sigma})\neq 1$ (therefore the multiplication
order is irrelevant).

###### Proof.

Every face of dimension larger than $1$ has a single core therefore
${F}({\sigma})\neq 1\Rightarrow{F}^{core\left({\sigma}\right)}({\sigma})\neq
1$. And for every other possible core it holds that ${F}^{c}({\sigma})=1$. In
addition:

${F}({\sigma})={F}^{core\left({\sigma}\right)}({\sigma})=\prod_{c\in
X(k-1)}{{F}^{c}({\sigma})}$

∎

######  Corollary 3.21.

For every cochain of dimension at least $1$: $\left\|{F}\right\|=\sum_{c\in
X(k-1)}{\left\|{F}^{c}\right\|}$

We will now show that the deconstruction of a cochain to a set of cochains is,
in a sense, independent. We will start by showing that the distance of a
cochain from the coboundaries can be derived by measuring the distance of the
cochain from the coboundaries around every core:

######  Lemma 3.22.

Let ${F}\in C^{i}\left(\hat{R}^{k}(X);G\right)$. If
${A}=\operatorname*{arg\,min}_{{B}\in
Z^{i}\left(\hat{R}^{k}(X);G\right)}{\left\|{F}{B}^{-1}\right\|}$ then for
every core $c$ it holds that ${A}^{c}=\operatorname*{arg\,min}_{{B}\in
Z^{i}\left(\hat{R}^{k}_{c}(X);G\right)}{\left\|{F}^{c}{B}^{-1}\right\|}$

###### Proof.

It is easy to see that for every possible core $c$ and any two cochains
${F}_{1},{F}_{2}$ it holds that
$({F}_{1}\cdot{F}_{2})^{c}={F}_{1}^{c}\cdot{F}_{2}^{c}$ and
$\left({F}^{-1}\right)^{c}=\left({F}^{c}\right)^{-1}$. In addition:

$\left\|{F}{A}^{-1}\right\|=\sum_{c\in
X(k-1)}{\left\|\left({F}{A}^{-1}\right)^{c}\right\|}=\sum_{c\in
X(k-1)}{\left\|{F}^{c}\left({A}^{-1}\right)^{c}\right\|}=\sum_{c\in
X(k-1)}{\left\|{F}^{c}\left({A}^{c}\right)^{-1}\right\|}$

We will complete the proof using the counter positive argument: Assume that
there exists a core $c^{\prime}$ in which
${L}=\operatorname*{arg\,min}_{{B}\in
Z^{i}\left(\hat{R}^{k}_{c^{\prime}}(X);G\right)}{\left\|{F}^{c^{\prime}}{B}^{-1}\right\|}$
and
$\left\|{F}^{c^{\prime}}{L}^{-1}\right\|<\left\|{F}^{c^{\prime}}\left({A}^{c^{\prime}}\right)^{-1}\right\|$.
Therefore consider the following cochain:

${A}^{\prime}({\sigma})=\begin{cases}{A}^{core\left({\sigma}\right)}({\sigma})&core\left({\sigma}\right)\neq
c^{\prime}\\\ {L}({\sigma})&\text{otherwise}\end{cases}$

Note that every face ${\tau}\in\hat{R}^{k}(X)(i+1)$ is completely contained in
$\hat{R}^{k}_{core\left({\tau}\right)}(X)$ and therefore if
$core\left({\tau}\right)\neq c^{\prime}$ then
$d_{1}{A}^{\prime}({\tau})=d_{1}{A}^{core\left({\tau}\right)}({\tau})=1$ and
otherwise $d_{1}{A}^{\prime}({\tau})=d_{1}{L}({\tau})=1$. Therefore
${A}^{\prime}$ is a cocycle. Also note that:

$\displaystyle\left\|{F}{A}^{\prime-1}\right\|$ $\displaystyle=\sum_{c\in
X(k-1)}{\left\|\left({F}{A}^{\prime-1}\right)^{c}\right\|}=\sum_{c\in
X(k-1)\setminus\left\\{c^{\prime}\right\\}}{\left\|{F}\left({A}^{c}\right)^{-1}\right\|}+\left\|{F}{L}^{-1}\right\|$
$\displaystyle<\sum_{c\in
X(k-1)}{\left\|\left({F}{A}^{-1}\right)^{c}\right\|}=\left\|{F}{A}^{-1}\right\|$

Which contradicts our choice of ${A}$. ∎

######  Lemma 3.23 (The representation around every core is an expander).

For every core $c$, $\hat{R}^{k}_{c}(X)$ is a $\gamma$-coboundary-expander.

###### Proof.

The representation complex around the core $c$ is isomorphic to the link of
$c$ in the original complex due to Lemma 3.16. $X_{c}$ is a
$\gamma$-coboundary-expander and therefore so is $\hat{R}^{k}_{c}(X)$. ∎

######  Lemma 3.24.

For every core $c$ and every cochain ${F}$ it holds that
$\left(d_{1}{F}\right)^{c}=d_{1}\left({F}^{c}\right)$

###### Proof.

Let ${F}\in C^{i}\left(X;G\right)$ for $i\geq 1$:

$\displaystyle\forall{\sigma}\in X(i+1):\left(d_{1}{F}\right)^{c}({\sigma})$
$\displaystyle=\begin{cases}d_{1}{F}({\sigma})&core\left({\sigma}\right)=c\\\
1&\text{otherwise}\end{cases}=\begin{cases}d_{1}{F}({\sigma})&core\left({\sigma}\right)=c\\\
d_{1}\mathbbm{1}({\sigma})&\text{otherwise}\end{cases}$
$\displaystyle=d_{1}\begin{cases}{F}({\sigma})&core\left({\sigma}\right)=c\\\
\mathbbm{1}({\sigma})&\text{otherwise}\end{cases}=d_{1}\left({F}^{c}\right)$

∎

######  Lemma 3.25 (The representation complex expands in the first
dimension).

For every cochain ${F}\in C^{1}\left(\hat{R}^{k}(X);G\right)$:

$\frac{\left\|d_{1}{F}\right\|}{\operatorname{dist}\left({F},Z^{1}\left(\hat{R}^{k}(X)_{\sigma};G\right)\right)}\geq\gamma$

###### Proof.

Due to Lemma 3.23 around every core the representation complex is a
$\gamma$-coboundary-expander. Let ${A}=\operatorname*{arg\,min}_{{B}\in
Z^{i}\left(\hat{R}^{k}_{c}(X);G\right)}{\left\|{F}{B}^{-1}\right\|}$.

$\displaystyle\left\|d_{1}{F}\right\|$ $\displaystyle=\sum_{c\in
X(k-1)}{\left\|d_{1}{F}^{c}\right\|}=\sum_{c\in\left\\{cores\right\\}}{t_{c}\left\|d_{1}{F}^{c}\right\|_{\hat{R}^{k}_{c}(X)}}$
$\displaystyle\geq\gamma\sum_{c\in
X(k-1)}{t_{c}\operatorname{dist}_{\hat{R}^{k}_{c}(X)}\left({F}^{c},Z^{i}\left(\hat{R}^{k}_{c}(X);G\right)\right)}=\gamma\sum_{c\in
X(k-1)}{t_{c}\left\|{A}^{c}\right\|_{\hat{R}^{k}_{c}(X)}}$
$\displaystyle=\gamma\sum_{c\in
X(k-1)}{\left\|{A}^{c}\right\|}=\gamma\left\|{A}\right\|=\gamma\operatorname{dist}\left({F},Z^{i}\left(\hat{R}^{k}_{c}(X)\right)\right)$

∎

We finish this section by noting that, despite the fact that the
representation complex’s cohomology is not trivial, the distance of a cochain
from the coboundaries can still be tested. This test will be further explored
in Appendix A where we prove the following lemma:

######  Lemma 3.26 (The Coboundaries of the Representation Complex are
Testable).

If $X$ is a $\gamma$-coboundary-expander then there exists a tester $T$ that
queries exactly $3$ edges141414We can claim something even stronger.
Specifically that $T$ picks three vertices and queries the edges between them.
and a constant $\eta=\eta(k,\gamma)$ such that:

$\operatorname{dist}\left({F},B^{1}\left(\hat{R}^{k}(X)\right)\right)\leq\eta\cdot\Pr\left[T\text{
rejects }{F}\right]$

##  4 On the Covers That Correspond to Coboundaries

Recall the connection between cocycles and cover spaces of a simplicial
complex. Specifically, recall that $Y_{Z}$ is a cover space of $X$ iff ${Z}$
is a cocycle. In this section we will be interested in the properties of cover
spaces that corresponds with coboundaries. We start by showing that, if ${Z}$
is a coboundary then the lift of any cycle $C$ in $X$ is a cycle in $Y_{Z}$:

######  Lemma 4.1 (Lifts of cycles are cycles).

Let ${\phi}\in B^{1}\left(X;G\right)$ and let $Y_{\phi}$ be a cover of $X$
with the simplicial map $f:Y_{\phi}\rightarrow X$. Also let
$C=({v}_{0},\dots,{v}_{i},{v}_{0})$ be a vertex-edge cycle in $X$. Then every
lift of $C$ is a cycle in the vertex in $Y_{\phi}$.

###### Proof.

Consider the lift of the cycle to the cover $Y_{\phi}$ and note that it is
comprised of the following edges (for some $s\in G$):

$\displaystyle\left\\{[{v}_{0},s],[{v}_{1},{\phi}({v}_{1},{v}_{0})s]\right\\},\left\\{[{v}_{1},{\phi}({v}_{1},{v}_{0})s],[{v}_{2},{\phi}({v}_{0},{v}_{1}){\phi}({v}_{1},{v}_{0})s]\right\\},$
$\displaystyle\dots,\left\\{[{v}_{i},\prod_{j=0}^{i-1}{{\phi}({v}_{j+1},{v}_{j})}s],[{v}_{0},{\phi}({v}_{0},{v}_{i})\prod_{j=0}^{i-1}{{\phi}({v}_{j+1},{v}_{j})}s]\right\\}$

Because ${\phi}$ is a coboundary there exists a $\psi\in C^{0}\left(X\right)$
such that
${\phi}({\sigma}_{1},{\sigma}_{2})=\psi({\sigma}_{1})\psi({\sigma}_{1})^{-1}$
therefore:

$\displaystyle{\phi}({v}_{0},{v}_{i})\prod_{j=0}^{i-1}{{\phi}({v}_{j+1},{v}_{j})}$
$\displaystyle=\psi({v}_{0})\psi({v}_{i})^{-1}\prod_{j=0}^{i-1}{\psi({v}_{j+1})\psi({v}_{j})^{-1}}$
$\displaystyle=\psi({v}_{0})\psi({v}_{i})^{-1}\psi({v}_{i})\psi({v}_{0})^{-1}=1$

Therefore the path starts and ends on the same vertex. ∎

We can show something even stronger, namely that the cover is actually
comprised of $l$ distinct instances of the original complex.

######  Lemma 4.2 (Cover decomposition).

Let ${\phi}\in B^{1}\left(X;G\right)$ and let $Y_{\phi}$ be a cover of $X$
then there exists $Y_{1},\dots,Y_{l}$ such that $Y_{\phi}=\mathaccent
0{\cdot}{\bigcup}_{i=1}^{l}{Y_{i}}$ and $Y_{1}\cong\cdots\cong Y_{l}\cong X$.

###### Proof.

$Y_{\phi}$ is a cover of $X$. ${\phi}$ is a coboundary therefore there exists
$\psi\in C^{0}\left(X;G\right)$ such that ${\phi}=d_{1}\psi$. We will show
that for any dimension $i$ and every face ${\sigma}\in Y_{\phi}(i)$ is of the
form
${\sigma}=\left\\{[{v}_{1},\psi({v}_{1})s],\dots,[{v}_{i},\psi({v}_{i})s]\right\\}$
such that $\left\\{{v}_{1},\dots,{v}_{i}\right\\}\in X(i)$. Note that if
$[{v}_{1},\psi({v}_{1})s]\in{\sigma}$ then the rest of the vertices in the
face are of the form:

$[{v}_{j},{\phi}({v}_{j},{v}_{1})\psi({v}_{1})s]=[{v}_{j},\psi({v}_{j})\psi({v}_{1})^{-1}\psi({v}_{1})s]=[{v}_{j},\psi({v}_{j})s]$

Consider the sub-complexes of $Y_{\phi}$ defined by:

$Y_{j}(i)=\left\\{\left\\{[{v}_{1},\psi({v}_{1})i],\dots,[{v}_{i},\psi({v}_{i})i]\right\\}\middle|\left\\{{v}_{1},\dots,{v}_{i}\right\\}\in
X(i)\right\\}$

It is easy to see that these are all simplicial complexes. We will now show
that they are distinct, that their union is $Y_{\phi}$ and that they are
indeed isomorphic to $X$.

Assume that $Y_{j_{1}}\cap Y_{j_{2}}\neq\left\\{\emptyset\right\\}$. Let
$[{v},k]$ be a vertex in $Y_{j_{1}}\cap Y_{j_{2}}$ (there must be one due to
the closure property of both complexes). Therefore
$\psi({v})j_{1}=k=\psi({v})j_{2}$ and therefore $j_{1}=j_{2}$ (due to the fact
that $\psi({v})\in G$ and therefore it has an inverse).

For every dimension $i$ let
$\left\\{[{v}_{1},\psi({v}_{1})s],\dots,[{v}_{i},\psi({v}_{i})s]\right\\}\in
Y_{\phi}(i)$. Note that $s\in S$ and
$\left\\{{v}_{1},\dots,{v}_{i}\right\\}\in X(i)$ and therefore
$\left\\{[{v}_{1},\psi({v}_{1})s],\dots,[{v}_{i},\psi({v}_{i})s]\right\\}\in
Y_{j}(i)$. It is easy to see that $Y_{j}\subseteq Y_{\phi}$ for every $j$.

For every $Y_{j}$ consider $f:X\rightarrow Y_{j}$ to be
$f(\left\\{{v}_{1},\dots,{v}_{i}\right\\})=\left\\{[{v}_{1},\psi({\sigma})j],\dots,[{v}_{i},\psi({\sigma})j]\right\\}$.
Notice that this is a bijection (with the inverse function being
$f^{-1}(\left\\{[{v}_{1},\psi({\sigma})j],\dots,[{v}_{i},\psi({\sigma})j]\right\\})=\left\\{{v}_{1},\dots,{v}_{i}\right\\}$).
In addition notice that if ${\sigma}_{1}\subseteq{\sigma}_{2}$ then
$f({\sigma}_{1})\subseteq f({\sigma}_{2})$. ∎

##  5 Local Assignments in the Original Complex Imply a Near Cover in the
Representation Complex

In this section we will show how to derive a near cover for the representation
complex from local assignments in the original complex. More specifically, we
will provide an algorithm that, given some edge, returns the edges that cover
it in the near cover. This cover will not only be helpful in separating the
complex to somewhat-consistent components but will also allow us to bound how
close each component is to being fully consistent.
Consider the following algorithm for querying the edges of the near cover:

1 Query the list functions on ${\sigma}_{1}$:
${\mathscr{{F}}}^{{\sigma}_{1}}_{1},\dots,{\mathscr{{F}}}^{{\sigma}_{1}}_{l}$.

2 Query the list functions on ${\sigma}_{2}$:
${\mathscr{{F}}}^{{\sigma}_{2}}_{1},\dots,{\mathscr{{F}}}^{{\sigma}_{2}}_{l}$.

3 if  _there exists $\pi$ such that for every
${v}\in{\sigma}_{1}\cap{\sigma}_{2}$ and every $i$ it holds that
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi(i)}({v})$_
then

4 return
$\left\\{\left\\{{\mathscr{{F}}}^{{\sigma}_{1}}_{i},{\mathscr{{F}}}^{{\sigma}_{2}}_{\pi(i)}\right\\}\middle|i\in\left[l\right]\right\\}$

5else

6 return
$\left\\{\left\\{{\mathscr{{F}}}^{{\sigma}_{1}}_{i},{\mathscr{{F}}}^{{\sigma}_{2}}_{i}\right\\}\middle|i\in\left[l\right]\right\\}$

7 end if

Algorithm 2 query cover edge ($\left\\{{\sigma}_{1},{\sigma}_{2}\right\\})$

Before we move on consider the following intuition to what Algorithm 2 does:
Effectively Algorithm 2 tries to find a matching between the lifts of
${\sigma}_{1}$ and ${\sigma}_{2}$ that could be extended into a coboundary.

We consider the near cover whose vertices are the assignments associated with
each $k$-face, its edges are the result of Algorithm 2 and we also complete
the cover upwards (i.e. if a higher dimensional face can be covered it will
be).
It will also be useful to have a way to distinguish between edges that satisfy
the condition in step 2 and those that are not.

######  Definition 5.1.

An adequately covered edge is an edge for which there exists a permutation
$\pi$ such that for every ${v}\in{\sigma}_{1}\cap{\sigma}_{2}$ and every $i$
it holds that
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi(i)}({v})$.

We can also check whether an edge is adequately covered:

1 Query the list functions on ${\sigma}_{1}$:
${\mathscr{{F}}}^{{\sigma}_{1}}_{1},\dots,{\mathscr{{F}}}^{{\sigma}_{1}}_{l}$.

2 Query the list functions on ${\sigma}_{2}$:
${\mathscr{{F}}}^{{\sigma}_{2}}_{1},\dots,{\mathscr{{F}}}^{{\sigma}_{2}}_{l}$.

return _whether there exists $\pi$ such that for every
${v}\in{\sigma}_{1}\cap{\sigma}_{2}$ and every $i$ it holds that
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi(i)}({v})$_

Algorithm 3 is adequately covered
($\left\\{{\sigma}_{1},{\sigma}_{2}\right\\})$

Now that we have defined the near cover implied by the functions on the
$k$-faces of the complex it is time to move on to present the test.

##  6 Presenting a Test for List Agreement

Now we are finally ready to present our test:

1 pick  _with probability 0.5_

2 Run the test guaranteed by Lemma 3.26. Whenever the test performs a query
run Algorithm 2 and provide the test with its answer.

3 Sample an edge in the representation complex and check whether it is
adequately covered (using Algorithm 3).

4

Algorithm 4 test for list agreement

######  Note.

We have shown in Lemma 3.14 that one can indeed sample from the representation
complex.

We will spend the rest of this section proving that this algorithm is indeed a
test for list agreement.

######  Theorem 6.1 (Main Theorem).

Algorithm 4 is a test for list agreement when the $l$-assignment is
$2$-locally-differing over a complex that is a 1-up agreement expander and
whose every link is a coboundary expander over the symmetric group with $l$
elements151515This includes the entire complex as it is the link of
$\emptyset$..

Before we prove the main theorem let us reiterate the proof’s strategy: We are
first going to use the connection between cochains and near covers in order to
claim that the near cover implied by the functions in the lists of the
$k$-faces is close to a genuine cover that correspond to a coboundary.
Consider the genuine cover that is close to that near cover - this cover can
be thought of as $l$ independent copies of the representation complex. Note
that because our near cover was made using the functions in the lists of the
different vertices each one of the copies in the cover can be thought of as
assigning each vertex of the representation complex with a single local
function. Also note that the vertices of the representation complex
corresponds to the $k$-faces of the original complex. Using this fact one can
think of each of the copies of the representation complex in the cover as an
assignment of a singular function to each of the $k$-faces of the original
complex. We would then proceed to estimate the distance of each of these
assignments of functions from being agreeing assignments. In an ideal setting
we would be able to run the 1-up agreement expander test described in [DK17]
on each of the copies and measure their rejection probability. Alas we do not
have access to query the genuine cover (and therefore the correct local
assignments for each vertices). What we can do, however, is bound from above
the rejection probability of these tests without running them. We do so by
first noting that the random choice done in that test corresponds to picking
an edge in the representation complex. Then consider when the agreement test
rejects an edge in the representation complex, this can happen in one of two
cases - Either the edge is not adequately covered161616Note that if the edge
is not adequately covered in the near cover then it is not adequately covered
in the cover. or the edge was adequately covered in the near cover but the
near cover and the cover differ on that edge. Using this fact we can bound
from above the probability that the 1-up agreement test rejects when given
access to each one of the copies of the representation complex. Therefore the
distance of each copy from having a global function can be estimated. This is
also a bound on the distance of the lists from having $l$ global functions
that agree with them.

######  Notation.

Denote by $Y$ the near cover generated by Algorithm 2 and by $\tilde{Y}$ a
genuine cover that is close to $Y$ and represents a coboundary (Specifically
the one guaranteed by Lemma 3.26). Also denote by
$f_{Y}:Y\rightarrow\hat{R}(X)$ the near covering map implied by Algorithm 2
and by $f_{\tilde{Y}}:\tilde{Y}\rightarrow\hat{R}(X)$ the covering map between
$\tilde{Y}$ and $\hat{R}(X)$. Lastly denote by
$\tilde{Y}_{1},\dots,\tilde{Y}_{l}$ the $l$ copies 171717Note that this is
indeed the structure of a cover that corresponds to a coboundary due to Lemma
4.2. of $\hat{R}(X)$ that make up $\tilde{Y}$ and by
$f_{\tilde{Y_{i}}}:\tilde{Y_{i}}\rightarrow\hat{R}(X)$ the restriction of the
covering map to the copy $i$.

######  Definition 6.2.

Let ${\mathscr{{F}}}$ be a $k$-dimensional $l$-assignment of $X$ and let
$\tilde{Y}$ be the cover of $X$ described above. Define
${\mathcal{{F}}}_{1},\dots,{\mathcal{{F}}}_{l}$ the sub-assignments of
${\mathscr{{F}}}$ implied by $Y$ to be assignments such that:

$\forall i\in[l]:\tilde{Y}_{i}(0)={\mathcal{{F}}}_{i}$

######  Notation.

Denote the set of inadequately covered edges of $\hat{R}(X)$ as
$I_{\hat{R}^{k}(X)}$.

######  Notation.

Denote by $A$ (stands for adjustment) the set of edges that are covered
differently between $Y$ and $\tilde{Y}$, formally:

$A=\left\\{{\sigma}\in\hat{R}^{k}(X)(1)\middle|f_{Y}^{-1}({\sigma})\neq
f_{\tilde{Y}}^{-1}({\sigma})\right\\}$

######  Definition 6.3.

Define $D_{i}$ the disagreeing edges of $\tilde{Y}_{i}$, formally:

$D_{i}=\left\\{\left\\{r_{1},r_{2}\right\\}\in\hat{R}^{k}(X)(1)\middle|{\mathcal{{F}}}_{i}^{r_{1}}|_{core\left(\left\\{r_{1},r_{2}\right\\}\right)}\neq{\mathcal{{F}}}_{i}^{r_{2}}|_{core\left(\left\\{r_{1},r_{2}\right\\}\right)}\right\\}$

Consider what happens when we run the 1-up agreement test on $X$ with the
$k$-dimensional assignments of ${\mathcal{{F}}}_{i}$. The 1-up agreement test
picks a $\left(k+1\right)$-dimensional face and then two of its $k$-subsets
and check whether the local assignment of the sub-faces from
${\mathcal{{F}}}_{i}$ agree on their intersection. Note that this is
completely equivalent to picking an edge in the representation complex (since,
as shown in Algorithm 1 this is exactly the process of sampling an edge in
$\hat{R}(X)$) and check whether the functions associated with its vertices
agree on the core of the edge. Therefore, when viewing the 1-up agreement test
through the lens of the representation complex the set of edges that the 1-up
agreement test rejects is exactly $D_{i}$. The following lemma is a formal
proof of this notion:

######  Lemma 6.4.

For every $\tilde{Y}_{i}$ if the 1-up agreement test rejects the edge
${\sigma}\in\hat{R}(X)$ then either ${\sigma}$ is inadequately covered or
${\sigma}$ is covered differently by $\tilde{Y}$ then it is covered by $Y$,
formally:

$D_{i}\subseteq A\cup I_{\hat{R}^{k}(X)}$

###### Proof.

Let $\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\in D_{i}$. Assuming that
$\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\notin A\cup I_{\hat{R}^{k}(X)}$
then, because $\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\notin A$ it holds
that
$f_{Y}^{-1}(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\})=f_{\tilde{Y}}^{-1}(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\})$.
In addition, because $\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\notin
I_{\hat{R}^{k}(X)}$ then ${\sigma}$ is adequately covered i.e.

$\forall\left\\{{\mathscr{{F}}}^{{\sigma}_{1}}_{i},{\mathscr{{F}}}^{{\sigma}_{2}}_{j}\right\\}\in
f_{Y}^{-1}({\sigma}):{\mathscr{{F}}}^{{\sigma}_{1}}_{i}|_{core\left(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\right)}={\mathscr{{F}}}^{{\sigma}_{2}}_{j}|_{core\left(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\right)}$

Therefore:

$\forall\left\\{{\mathscr{{F}}}^{{\sigma}_{1}}_{i},{\mathscr{{F}}}^{{\sigma}_{2}}_{j}\right\\}\in
f_{\tilde{Y}}^{-1}({\sigma}):{\mathscr{{F}}}^{{\sigma}_{1}}_{i}|_{core\left(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\right)}={\mathscr{{F}}}^{{\sigma}_{2}}_{j}|_{core\left(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\right)}$

Which contradicts the fact that ${\sigma}\in D_{i}$. ∎

######  Lemma 6.5.

Let $X$ be a $\gamma$-coboundary-expander and $\alpha$-agreement-expander.
Also let $\eta=\eta(k,\gamma)$ be the constant from Lemma 3.26 then for every
$l$-assignment ${\mathscr{{F}}}$ it holds that:

$\frac{\eta}{2\eta+2}\frac{\alpha}{k}\cdot\operatorname{dist}\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}}\right)\leq\Pr\left[\text{Algorithm~{}\ref{alg:test-
for-list-agreement} rejects}\right]$

###### Proof.

$\displaystyle\operatorname{dist}\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}}\right)$
$\displaystyle\leq\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}\left({\mathcal{{F}}}_{i},\boldsymbol{{\mathcal{{A}}}}\right)}\leq\frac{1}{l}\sum_{i=1}^{l}{\frac{k}{\alpha}\left\|D_{i}\right\|}\leq\frac{1}{l}\sum_{i=1}^{l}{\frac{k}{\alpha}\left\|A\cup
I_{\hat{R}^{k}(X)}\right\|}\leq\frac{k}{\alpha}\left\|A\cup
I_{\hat{R}^{k}(X)}\right\|$

Note that step 4 of Algorithm 4 picks an edge in $\hat{R}^{k}(X)$ and checks
whether it is in $A$ therefore:

$\left\|I_{\hat{R}^{k}(X)}\right\|=\Pr\left[\text{Step~{}\ref{alg:list-
agreement:edges-are-adequatly-covered} of Algorithm~{}\ref{alg:test-for-list-
agreement} rejects}\right]$

In addition due to Lemma 3.26 it holds that:

$\eta\left\|A\right\|\leq\Pr\left[\text{Step~{}\ref{alg:list-
agreement:triangle-test} of Algorithm~{}\ref{alg:test-for-list-agreement}
rejects}\right]$

If algorithm 4 rejects with probability $\epsilon$ then both
$\Pr\left[\text{Step~{}\ref{alg:list-agreement:triangle-test} of
algorithm~{}\ref{alg:test-for-list-agreement} rejects}\right]\leq 2\epsilon$
and $\Pr\left[\text{Step~{}\ref{alg:list-agreement:edges-are-adequatly-
covered} of algorithm~{}\ref{alg:test-for-list-agreement} rejects}\right]\leq
2\epsilon$ and therefore:

$\displaystyle\left\|A\cup I_{\hat{R}^{k}(X)}\right\|$
$\displaystyle\leq\left\|A\right\|+\left\|I_{\hat{R}^{k}(X)}\right\|$
$\displaystyle\leq\frac{1}{\eta}\Pr\left[\text{Step~{}\ref{alg:list-
agreement:triangle-test} of algorithm~{}\ref{alg:test-for-list-agreement}
rejects}\right]+\Pr\left[\text{Step~{}\ref{alg:list-agreement:edges-are-
adequatly-covered} of algorithm~{}\ref{alg:test-for-list-agreement}
rejects}\right]$ $\displaystyle\leq 2\left(\frac{1}{\eta}+1\right)\epsilon$

Hence:

$\operatorname{dist}\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}}\right)\leq
2\frac{k}{\alpha}\left(\frac{1}{\eta}+1\right)\epsilon=\left(\frac{2\eta+2}{\eta\alpha}\right)\epsilon$

Therefore:

$\frac{\eta}{2\eta+2}\frac{\alpha}{k}\operatorname{dist}\left({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}}\right)\leq\epsilon$

∎

We will now move on to prove that Algorithm 4 accepts with probability $1$ any
agreeing $2$-locally-differing $l$-assignment. Before we do that, however, let
us start by examining the results of Algorithm 2:

######  Lemma 6.6 ($\pi$ found in Algorithm 2 is singular).

Let ${\mathscr{{F}}}$ be a $2$-locally-differing $l$-assignment. If Algorithm
2 finds a permutation $\pi$ in step 2 when given access to ${\mathscr{{F}}}$
then it is singular.

###### Proof.

We will use the counter positive argument - assume that there exists two
permutations $\pi_{1}$ and $\pi_{2}$ ($\pi_{1}\neq\pi_{2}$) such that for
every ${v}\in{\sigma}_{1}\cap{\sigma}_{2}$ and every $i$ it holds that
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi_{1}(i)}({v})$
and
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi_{2}(i)}({v})$.
Let $i$ be an integer such that $\pi_{1}(i)\neq\pi_{2}(i)$ and note that for
every vertex ${v}\in{\sigma}_{1}\cap{\sigma}_{2}$ it holds that:

${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi_{1}(i)}({v})={\mathscr{{F}}}^{{\sigma}_{1}}_{\pi_{2}^{-1}(\pi_{1}(i))}({v})$

Note that because
$\left|{\sigma}_{1}\cap{\sigma}_{2}\right|=\left|{\sigma}_{1}\right|-1$ it
holds that there exists at most one vertex ${v}^{\prime}$ such that
${\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v}^{\prime})\neq{\mathscr{{F}}}^{{\sigma}_{1}}_{\pi_{2}^{-1}(\pi_{1}(i))}({v}^{\prime})$
which contradicts the fact that ${\mathscr{{F}}}$ is locally differing. ∎

We are now ready to prove the lemma:

######  Lemma 6.7.

If ${\mathscr{{F}}}$ is an agreeing and $2$-locally-differing $k$-dimensional
$l$-assignment then it passes the test with probability $1$.

###### Proof.

In order to show that the $l$-assignment passes the test with probability $1$
we will first show that every edge is adequately covered and find the nature
of the permutation $\pi$ found by Algorithm 2. Then we will use this in order
to show that the test always accepts.

${\mathscr{{F}}}$ is an agreeing assignment therefore there exists
${\mathcal{{F}}}_{1},\cdots,{\mathcal{{F}}}_{l}$ such that for every face
${\sigma}\in X(k)$ there exists a permutation $\pi_{\sigma}$ such that for
every $i$ it holds that:

${\mathcal{{F}}}_{i}|_{{\sigma}}={\mathscr{{F}}}^{\sigma}_{\pi_{\sigma}(i)}$

Therefore at step 2 Algorithm 2 finds
$\pi=\pi_{{\sigma}_{2}}\pi_{{\sigma}_{1}}^{-1}$ due to the fact that $\pi$ is
singular and for every $i$ it holds that:

$\forall{v}\in{\sigma}_{1}\cap{\sigma}_{2}:{\mathscr{{F}}}^{{\sigma}_{1}}_{i}({v})={\mathcal{{F}}}_{\pi_{{\sigma}_{1}}^{-1}(i)}({v})={\mathscr{{F}}}^{{\sigma}_{2}}_{\pi_{{\sigma}_{2}}(\pi_{{\sigma}_{1}}^{-1}(i))}({v})$

This immediately implies that every edge is adequately covered and that the
cochain created by Algorithm 2 is a coboundary. Therefore, if Algorithm 4
checks if an edge is adequately covered then it accepts since every edge is
adequately covered. Otherwise Algorithm 4 checks whether the cochain generated
by Algorithm 2 is a coboundary and therefore it accepts with probability $1$.
∎

We are now finally ready to prove the main theorem:

###### Proof of Theorem 6.1.

In order to calculate the cover over each edge in the representation complex
all the local assignments of both vertices are queried. The empty triangle
test queries a triangle (either empty or proper) and therefore it queries $3$
edges using Algorithm 2. Each run of Algorithm 2 requires $2l$ queries
however, some vertices are queried twice, therefore we can reduce the query
complexity of this step to $3l$. Checking whether an edge is adequately
covered takes $2l$ queries (using the same argument). Therefore algorithm 4
queries ${\mathscr{{F}}}$ at most $3l$ times. We finish the proof by noting
that the fact that algorithm 4 is indeed a test for whether the $l$-assignment
is agreeing stems directly from Lemma 6.5 and Lemma 6.7. ∎

We therefore conclude that Algorithm 4 is a test for list agreement expansion
in the $2$-differing case. We note that the test’s distance improves as the
complex is a better agreement expander and coboundary expander as well as when
the dimension of the local assignments decrease.

Note that, in fact, we could have proven a more general statement then the
main theorem which we will now present. Before we do that, however, we have to
define the test graph of an agreement tester:

######  Definition 6.8 (Test Graph).

Let $X$ be a simplicial complex and let $T$ be an agreement test on the $k$th
dimensional faces of $X$. Given a set of local functions
$\left\\{f_{{\sigma}}:{\sigma}\rightarrow\left\\{0,1\right\\}\right\\}_{{\sigma}\in
X(d)}$ the test picks two faces
$\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\sim\mathcal{D}$ and checks whether
$f_{{\sigma}_{1}}|_{{\sigma}_{1}\cap{\sigma}_{2}}=f_{{\sigma}_{2}}|_{{\sigma}_{1}\cap{\sigma}_{2}}$.
Define the test graph of the test $T$ to be the weighted graph $G=(V,E,w_{T})$
such that:

  * •

$V=X(k)$

  * •

$E=\left\\{\left\\{{\sigma}_{1},{\sigma}_{2})\right\\}\middle|\Pr_{\left\\{{\tau}_{1},{\tau}_{2}\right\\}\sim\mathcal{D}}\left[{{\tau}_{1}={\sigma}_{1}\text{
and }{\tau}_{2}={\sigma}_{2}}\right]>0\right\\}$

  * •

$w_{T}(\left\\{{\sigma}_{1},{\sigma}_{2})\right\\})=\Pr_{\left\\{{\tau}_{1},{\tau}_{2}\right\\}\sim\mathcal{D}}\left[{{\tau}_{1}={\sigma}_{1}\text{
and }{\tau}_{2}={\sigma}_{2}}\right]$

######  Theorem 6.9 (Main Theorem, Generalized).

Let $X$ be a simplicial complex and let $T$ be an agreement test on the $k$-th
dimensional faces of $X$. Then if the test graph of $T$ is a $1$-skeleton of a
coboundary expander with respect to $S_{l}$ (denoted $X^{\prime}$) such that
$w_{T}(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\})=\operatorname{w}_{X^{\prime}}\left(\left\\{{\sigma}_{1},{\sigma}_{2}\right\\}\right)$
and there exists an algorithm that queries the test graph then Algorithm 4 is
a test for $l$-agreement over $X(k)$.

##  7 On the $2$-Differing Assumption

In this section we discuss the $2$-differing assumption that we made on
assignments. Specifically we will show some lower bounds on the number of
queries required in order to test list agreement in complexes of interest. Our
main tool for proving this lower bound is the following Lemma:

######  Notation 7.1.

Let ${\mathscr{{F}}}$ and let $q$ be a possible query for ${\mathscr{{F}}}$.
Denote by ${\mathscr{{F}}}[q]$ the result of performing the query $q$ on
${\mathscr{{F}}}$.

######  Lemma 7.2.

Let ${\mathscr{{R}}}$ be a non-agreeing $l$-assignment. Suppose that for any
set of $p$ queries $q_{1},\cdots,q_{p}$ there exists an agreeing assignment
${\mathscr{{A}}}_{\left(q_{1},\cdots,q_{p}\right)}$ such that:

$\forall
i\in\left\\{1,\cdots,p\right\\}:{\mathscr{{R}}}[q_{i}]={\mathscr{{A}}}_{\left(q_{1},\cdots,q_{o}\right)}[q_{i}]$

then there is no test that tests $l$-agreement and queries the assignment only
$p$ times.

###### Proof.

We will show that the test always accepts when given oracle access to
${\mathscr{{R}}}$ and therefore ${\mathscr{{R}}}$ should be an agreeing
assignment despite the fact that it is not. Assume that there is a test $T$
that queries only $p$ location of the $l$-assignment and accepts with
probability $1$ iff the $l$-assignment is agreeing. Denote by
$T^{\mathscr{{F}}}(r)$ running the test $T$ with oracle access to
${\mathscr{{F}}}$ and random bits $r$. Also, for every set of queries $T$
performs on ${\mathscr{{F}}}$ define by
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{p}\right)}$ the agreeing assignment
promised by the lemma. Note that the even if $T$ is an adaptive tester its
$i$-th query only depends on its random bits and the first $(i-1)$ queries.
Therefore for every $r$ let $\left(q_{1}^{r},\cdots,q_{p}^{r}\right)$ be the
queries performed in $T^{\mathscr{{R}}}(r)$ and note that:

$\forall
r:T^{{\mathscr{{R}}}}(r)=T^{{\mathscr{{A}}}_{\left(q_{1}^{r},\dots,q_{p}^{r}\right)}}(r)=1$

Which contradicts the fact that ${\mathscr{{R}}}$ is not an agreeing
$l$-assignment ∎

We then use Lemma 7.2 to test $2$-colorings or lack of $2$-colourings in
even/odd cycles in the complex. It is therefore convenient to define the
following:

######  Definition 7.3 (Coloring candidate).

A $2$-assignment is a coloring candidate for a simple cycle (or coloring
candidate in short) if the following conditions hold:

  * •

Any edge in the cycle is assigned either
$\left[{v}=0,{u}=1\right],\left[{v}=1,{u}=0\right]$ or
$\left[{v}=1,{u}=1\right],\left[{v}=0,{u}=0\right]$.

  * •

Any edge with one side in the cycle is assigned
$\left[{v}=1,{u}=0\right],\left[{v}=0,{u}=0\right]$.

  * •

Any edge whose both sides are not in the cycle is assigned
$\left[{v}=0,{u}=0\right],\left[{v}=0,{u}=0\right]$.

Consider the following coloring candidates:

######  Definition 7.4.

Let $X$ be a simplicial complex and let
$\gamma=\left(\gamma_{0},\cdots,\gamma_{n}\right)$ be a simple cycle in $X$
(when considering $X$ as not oriented). Given two vertices in the cycle
${v}_{1},{u}_{2}$ denote the distance between them on the cycle as
$\operatorname{dist}_{\gamma}\left({v}_{1},{u}_{2}\right)$ and the distance on
the cycle when not counting the edge
$\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ as
$\operatorname{dist}_{\gamma,k}\left({v}_{1},{u}_{2}\right)$. Define the
following two coloring candidates:

${\mathscr{{F}}}_{\gamma}^{e}\left(\left\\{{v},{u}\right\\}\right)=\begin{cases}\left[{v}=0,{u}=1\right],\left[{v}=1,{u}=0\right]&\exists
i,j:{v}=\gamma_{i},{u}=\gamma_{j},\operatorname{dist}_{\gamma}\left({v}_{1},{u}_{2}\right)\text{
is odd}\\\ \left[{v}=0,{u}=0\right],\left[{v}=1,{u}=1\right]&\exists
i,j:{v}=\gamma_{i},{u}=\gamma_{j},\operatorname{dist}_{\gamma}\left({v}_{1},{u}_{2}\right)\text{
is even}\\\ \left[{v}=1,{u}=0\right],\left[{v}=0,{u}=0\right]&\exists i\forall
j:{v}=\gamma_{i},{u}\neq\gamma_{j}\\\
\left[{v}=0,{u}=0\right],\left[{v}=0,{u}=0\right]&\forall
i:{v}=\gamma_{i},{u}\neq\gamma_{i}\\\ \end{cases}\\\
{\mathscr{{F}}}_{\gamma,k}^{o}\left(\left\\{{v},{u}\right\\}\right)=\begin{cases}\left[{v}=1,{u}=1\right],\left[{v}=0,{u}=0\right]&{v}=\gamma_{k},{u}=\gamma_{k+1}\\\
\left[{v}=0,{u}=1\right],\left[{v}=1,{u}=0\right]&\exists
i,j:{v}=\gamma_{i},{u}=\gamma_{j},\operatorname{dist}_{\gamma,k}\left({v}_{1},{u}_{2}\right)\text{
is odd},(i,j)\neq(k,k+1)\\\
\left[{v}=0,{u}=0\right],\left[{v}=1,{u}=1\right]&\exists
i,j:{v}=\gamma_{i},{u}=\gamma_{j},\operatorname{dist}_{\gamma,k}\left({v}_{1},{u}_{2}\right)\text{
is even}\\\ \left[{v}=1,{u}=0\right],\left[{v}=0,{u}=0\right]&\exists i\forall
j:{v}=\gamma_{i},{u}\neq\gamma_{j}\\\
\left[{v}=0,{u}=0\right],\left[{v}=0,{u}=0\right]&\forall
i:{v}=\gamma_{i},{u}\neq\gamma_{i}\end{cases}$

We think of ${\mathscr{{F}}}_{\gamma}^{e}$ as a $2$-assignment that attempts
to color the vertices of $\gamma$ in two colors. Likewise we think of
${\mathscr{{F}}}_{\gamma}^{o}$ as a $2$-assignment that “glues together”
$\gamma_{0}$ and $\gamma_{1}$ and then tries to color the rest of the graph in
two colors.

######  Example 7.5.

Consider the following graphs as parts of the $1$-skeleton of some simplicial
complex. Our first example is of ${\mathscr{{F}}}_{\gamma}^{e}$:

$\gamma_{0}$$\gamma_{1}$$\gamma_{2}$$\gamma_{3}$$\gamma_{4}$$\gamma_{5}$${v}_{5}$${v}_{0}$${v}_{1}$${v}_{2}$${v}_{3}$${v}_{4}$$\begin{subarray}{c}\gamma_{0}=0,\gamma_{1}=1\\\
\gamma_{0}=1,\gamma_{1}=0\end{subarray}$$\begin{subarray}{c}\gamma_{1}=1,\gamma_{2}=0\\\
\gamma_{1}=0,\gamma_{2}=1\end{subarray}$$\begin{subarray}{c}\gamma_{3}=0,\gamma_{2}=1\\\
\gamma_{3}=1,\gamma_{2}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=1,\gamma_{3}=0\\\
\gamma_{4}=0,\gamma_{3}=1\end{subarray}$$\begin{subarray}{c}\gamma_{5}=0,\gamma_{4}=1\\\
\gamma_{5}=1,\gamma_{4}=0\end{subarray}$$\begin{subarray}{c}\gamma_{5}=1,\gamma_{0}=0\\\
\gamma_{5}=0,\gamma_{0}=1\end{subarray}$$\begin{subarray}{c}\gamma_{0}=1,{v}_{0}=0\\\
\gamma_{0}=0,{v}_{0}=0\end{subarray}$$\begin{subarray}{c}{v}_{0}=0,\gamma_{1}=0\\\
{v}_{0}=0,\gamma_{1}=1\end{subarray}$$\begin{subarray}{c}\gamma_{1}=0,{v}_{1}=0\\\
\gamma_{1}=1,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}{v}_{1}=0,\gamma_{2}=1\\\
{v}_{1}=0,\gamma_{2}=0\end{subarray}$$\begin{subarray}{c}\gamma_{2}=1,{v}_{1}=0\\\
\gamma_{2}=0,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}\gamma_{3}=1,{v}_{2}=0\\\
\gamma_{3}=0,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{3}=0,\gamma_{3}=1\\\
{v}_{3}=0,\gamma_{3}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=0,{v}_{2}=0\\\
\gamma_{4}=1,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,\gamma_{4}=0\\\
{v}_{4}=0,\gamma_{4}=1\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,\gamma_{5}=0\\\
{v}_{4}=0,\gamma_{5}=1\end{subarray}$$\begin{subarray}{c}\gamma_{5}=0,{v}_{5}=0\\\
\gamma_{0}=1,{v}_{5}=0\end{subarray}$$\begin{subarray}{c}{v}_{5}=0,\gamma_{0}=1\\\
{v}_{5}=0,\gamma_{0}=0\end{subarray}$$\begin{subarray}{c}{v}_{0}=0,{v}_{1}=0\\\
{v}_{0}=0,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}{v}_{3}=0,{v}_{2}=0\\\
{v}_{3}=0,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,{v}_{3}=0\\\
{v}_{4}=0,{v}_{3}=0\end{subarray}$$\begin{subarray}{c}{v}_{5}=0,{v}_{0}=0\\\
{v}_{5}=0,{v}_{0}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=1,\gamma_{0}=1\\\
\gamma_{4}=0,\gamma_{0}=0\end{subarray}$$\begin{subarray}{c}\gamma_{0}=1,\gamma_{3}=0\\\
\gamma_{0}=0,\gamma_{3}=1\end{subarray}$

Note that the assignment is $2$-agreeing. We move on to demonstrate the odd
case, consider the same graph with the $2$-assignment
${\mathscr{{F}}}_{\gamma,0}^{o}$:

$\gamma_{0}$$\gamma_{1}$$\gamma_{2}$$\gamma_{3}$$\gamma_{4}$$\gamma_{5}$${v}_{5}$${v}_{0}$${v}_{1}$${v}_{2}$${v}_{3}$${v}_{4}$$\begin{subarray}{c}\gamma_{0}=1,\gamma_{1}=1\\\
\gamma_{0}=0,\gamma_{1}=0\end{subarray}$$\begin{subarray}{c}\gamma_{1}=1,\gamma_{2}=0\\\
\gamma_{1}=0,\gamma_{2}=1\end{subarray}$$\begin{subarray}{c}\gamma_{3}=0,\gamma_{2}=1\\\
\gamma_{3}=1,\gamma_{2}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=1,\gamma_{3}=0\\\
\gamma_{4}=0,\gamma_{3}=1\end{subarray}$$\begin{subarray}{c}\gamma_{5}=0,\gamma_{4}=1\\\
\gamma_{5}=1,\gamma_{4}=0\end{subarray}$$\begin{subarray}{c}\gamma_{5}=1,\gamma_{0}=0\\\
\gamma_{5}=0,\gamma_{0}=1\end{subarray}$$\begin{subarray}{c}\gamma_{0}=1,{v}_{0}=0\\\
\gamma_{0}=0,{v}_{0}=0\end{subarray}$$\begin{subarray}{c}{v}_{0}=0,\gamma_{1}=0\\\
{v}_{0}=0,\gamma_{1}=1\end{subarray}$$\begin{subarray}{c}\gamma_{1}=0,{v}_{1}=0\\\
\gamma_{1}=1,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}{v}_{1}=0,\gamma_{2}=1\\\
{v}_{1}=0,\gamma_{2}=0\end{subarray}$$\begin{subarray}{c}\gamma_{2}=1,{v}_{1}=0\\\
\gamma_{2}=0,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}\gamma_{3}=1,{v}_{2}=0\\\
\gamma_{3}=0,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{3}=0,\gamma_{3}=1\\\
{v}_{3}=0,\gamma_{3}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=0,{v}_{2}=0\\\
\gamma_{4}=1,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,\gamma_{4}=0\\\
{v}_{4}=0,\gamma_{4}=1\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,\gamma_{5}=0\\\
{v}_{4}=0,\gamma_{5}=1\end{subarray}$$\begin{subarray}{c}\gamma_{5}=0,{v}_{5}=0\\\
\gamma_{0}=1,{v}_{5}=0\end{subarray}$$\begin{subarray}{c}{v}_{5}=0,\gamma_{0}=1\\\
{v}_{5}=0,\gamma_{0}=0\end{subarray}$$\begin{subarray}{c}{v}_{0}=0,{v}_{1}=0\\\
{v}_{0}=0,{v}_{1}=0\end{subarray}$$\begin{subarray}{c}{v}_{3}=0,{v}_{2}=0\\\
{v}_{3}=0,{v}_{2}=0\end{subarray}$$\begin{subarray}{c}{v}_{4}=0,{v}_{3}=0\\\
{v}_{4}=0,{v}_{3}=0\end{subarray}$$\begin{subarray}{c}{v}_{5}=0,{v}_{0}=0\\\
{v}_{5}=0,{v}_{0}=0\end{subarray}$$\begin{subarray}{c}\gamma_{4}=1,\gamma_{0}=1\\\
\gamma_{4}=0,\gamma_{0}=0\end{subarray}$$\begin{subarray}{c}\gamma_{0}=1,\gamma_{3}=1\\\
\gamma_{0}=0,\gamma_{3}=0\end{subarray}$

Note that ${\mathscr{{F}}}_{\gamma,0}^{o}$ is _not_ $2$-agreeing.

We will move on to show that the agreement or lack thereof in the example is
solely dependent on the parity of the length of the cycle.

######  Lemma 7.6.

Let $X$ be a simplicial complex and let $\gamma$ be a simple cycle in $X$.
Then the following two statements hold:

  * •

${\mathscr{{F}}}^{e}_{\gamma}$ is agreeing iff $\gamma$ is of even length.

  * •

For every value of $k$: ${\mathscr{{F}}}^{o}_{\gamma,k}$ is agreeing iff
$\gamma$ is of odd length.

###### Proof.

We will start by showing that the claim holds for
${\mathscr{{F}}}^{e}_{\gamma}$: $\gamma$ is even iff it is bi-partite, let
$V_{1},V_{2}$ be the two parts of the cycle. We construct the following global
cochains ${F}_{1},{F}_{2}$:

${F}_{1}({v})=\begin{cases}s(\gamma_{i})&{v}=\gamma_{i}\\\
0&\text{otherwise}\end{cases}\qquad\qquad\qquad{F}_{2}({v})=\begin{cases}1-s(\gamma_{i})&{v}=\gamma_{i}\\\
0&\text{otherwise}\end{cases}$

It is east to see that ${\mathscr{{F}}}^{e}_{\gamma}$ is an agreeing
$2$-assignment that agrees with ${F}_{1}$ and ${F}_{2}$.

The proof of the statment for the odd case follows very similar arguments and
is therefore omitted. ∎

We consider a subset of all simple cycles defined below:

######  Definition 7.7 (Skipping edge).

Let $X$ be a simplicial complex and let $\gamma$ be a simple cycle in $X$.
Also let $e,e^{\prime}$ be edges such that there exists $i,j,k$ such that
$e=\left\\{\gamma_{i},\gamma_{j}\right\\},e^{\prime}=\left\\{\gamma_{k},\gamma_{k+1}\right\\}$.
We say that $e$ skips $e^{\prime}$ if
$\operatorname{dist}_{\gamma}\left(\gamma_{i},\gamma_{j}\right)=\operatorname{dist}_{\gamma}\left(\gamma_{i},\gamma_{k}\right)+\operatorname{dist}_{\gamma}\left(\gamma_{k},\gamma_{j}\right)+1$.

######  Definition 7.8 (Non-skipping cycle).

Let $X$ be a simplicial complex and let $\gamma$ be a simple cycle in the
underlying graph of the complex. We say that $\gamma$ is $i$-non-skipping if
for every $j,k$ such that $e=\left\\{\gamma_{j},\gamma_{k}\right\\}\in X(1)$
it holds that $e$ skips at most $i$ edges.

######  Definition 7.9 (Gluing).

Let $X$ be a simplicial complex, $\gamma$ be a simple cycle and
${\mathscr{{F}}}_{\gamma}$ be a coloring candidate. Define the gluing of its
$k$-edge as $glue_{k}({\mathscr{{F}}})$ to be a $2$-assignment such that:

  * •

Any edge that does not skip $\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ is left
unchanged.

  * •

The edge $\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ is assigned
$\left[{v}=1,{u}=1\right],\left[{v}=0,{u}=0\right]$.

  * •

Any edge that skipped $\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ and was
assigned $\left[{v}=0,{u}=1\right],\left[{v}=1,{u}=0\right]$ will be assigned
$\left[{v}=1,{u}=1\right],\left[{v}=0,{u}=0\right]$.

  * •

Any edge that skipped $\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ and was
assigned $\left[{v}=1,{u}=1\right],\left[{v}=0,{u}=0\right]$ will be assigned
$\left[{v}=0,{u}=1\right],\left[{v}=1,{u}=0\right]$.

######  Lemma 7.10.

Let $X$ be a simplicial complex, $\gamma$ be a simple cycle. Then for every
$j\neq k$: ${\mathscr{{F}}}^{o}_{\gamma,k}$ is agreeing iff
$glue_{j}\left({\mathscr{{F}}}^{o}_{\gamma,k}\right)$ is not agreeing.

###### Proof.

Consider ${\mathscr{{F}}}^{o}_{\gamma,k}$. Note that it is agreeing iff
$\gamma$ is of odd length. It will therefore suffice to prove that
$glue_{j}\left({\mathscr{{F}}}^{o}_{\gamma,k}\right)$ is only agreeing if the
cycle is of even length. Note that, by the definition of gluing,
$glue_{j}\left({\mathscr{{F}}}^{o}_{\gamma,k}\right)$ is agreeing iff
${\mathscr{{F}}}^{o}_{\gamma^{\prime},k}$ is agreeing where $\gamma^{\prime}$
is $\gamma$ with $\gamma_{j}$ and $\gamma_{j+1}$ “glued together” (i.e.
considered to be one vertex). Therefore
${\mathscr{{F}}}^{o}_{\gamma^{\prime},k}$ is agreeing iff $\gamma^{\prime}$ is
of odd length and thus $glue_{j}\left({\mathscr{{F}}}^{o}_{\gamma,k}\right)$
is agreeing iff $\gamma$ is of even length. ∎

We now show that the existence of a non-skipping in the complex yields a lower
bound on the number of queries required to test list agreement.

######  Lemma 7.11.

Let $X$ be a simplicial complex and let $\gamma$ be an $i$-non-skipping simple
cycle in $X$. Then there is a lower bound of $\frac{\left|\gamma\right|}{i}$
queries that _must_ be performed in order to test list agreement.

###### Proof.

We will show that it is impossible to distinguish between
${\mathscr{{F}}}^{e}_{\gamma}$ and ${\mathscr{{F}}}^{o}_{\gamma}$ using less
than $\frac{\left|\gamma\right|}{i}$ queries. Assume, by way of contradiction,
that there exists a test $T$ that distinguishes between
${\mathscr{{F}}}^{e}_{\gamma}$ and ${\mathscr{{F}}}^{o}_{\gamma}$ using less
than $\frac{\left|\gamma\right|}{i}$ queries.

Note that querying any edge whose vertices are not part of the cycle does not
help in distinguishing between ${\mathscr{{F}}}^{e}_{\gamma}$ and
${\mathscr{{F}}}^{o}_{\gamma}$. We can therefore assume that $T$ only queries
edges that are a part of the cycle (or a skipping edge). Let
$q_{1},\cdots,q_{\frac{\left|\gamma\right|}{i}-1}$ be the faces queried by
$T$. Consider the structure of these queries and note that there exists an
edge $e=\left\\{\gamma_{k},\gamma_{k+1}\right\\}$ that none of the queries
skip as the queries skip at most $\left|\gamma\right|-i$ edges and the length
of the cycle is strictly larger than that. The following holds:

  * •

If $\gamma$ is of odd length, note that performing
$q_{1},\cdots,q_{\frac{\left|\gamma\right|}{i}-1}$ on
${\mathscr{{F}}}^{e}_{\gamma}$ and ${\mathscr{{F}}}^{o}_{\gamma,k}$ yield the
same results.

  * •

If $\gamma$ is of even length, note that ${\mathscr{{F}}}^{o}_{\gamma,0}$ is
not an agreeing $2$-assignment. Also note that if
$e=\left\\{\gamma_{0},\gamma_{1}\right\\}$ then performing
$q_{1},\cdots,q_{\frac{\left|\gamma\right|}{i}-1}$ on
${\mathscr{{F}}}^{o}_{\gamma,0}$ and ${\mathscr{{F}}}^{e}_{\gamma}$ yield the
same results. In addition, if $e\neq\left\\{\gamma_{0},\gamma_{1}\right\\}$
then performing $q_{1},\cdots,q_{\frac{\left|\gamma\right|}{i}-1}$ on
${\mathscr{{F}}}^{o}_{\gamma,0}$ and
$glue_{k}\left({\mathscr{{F}}}^{o}_{\gamma,0}\right)$ yield the same results.

We can therefore finish the proof by applying Lemma 7.2. ∎

######  Remark 7.12.

In Lemma 7.11 we used a different querying model to the model we have been