using in the rest of the paper: In the model of queries we used in Lemma 7.11
a query accepts a face and returns _all_ of its assignments while in the rest
of the paper we used a model where each assignment is queried on its own. It
is easy to see that a lower bound on the number of queries performed in Lemma
7.11 holds for the model used at the rest of the paper (As one can think of
queries in the former model as queries in the latter model that get some
additional “free” information).

The rest of this section is dedicated to showing that complexes of interest
have _non-constant_ non-skipping cycles and thus without the $2$-differing
assumption they have no test for list agreement that performs a constant
number of queries.

###  7.1 Homology and List Agreement Testing Without the $2$-Differing
Assumption

One property of interest for high dimensional expanders is their homology. We
show that a lower bound on the homology of the complex yield a lower bound on
the number of queries required in order to test list agreement. It is
important to stress that, while the complexes that this result applies to have
no non-zero members of the homology, there are many complexes of interest
whose minimal non-zero member of the homology is growing with the size of the
complex. We begin by defining the homology of the complex.

######  Definition 7.13 (Boundary operator).

Given a cochain ${F}\in C^{k}\left(X;\mathbbm{F}_{2}\right)$ define the
boundary $\partial_{k}:C^{k}\left(X;\mathbbm{F}_{2}\right)\rightarrow
C^{k-1}\left(X;\mathbbm{F}_{2}\right)$ operator:

$\forall{\sigma}\in
X(k-1):\partial_{k}{F}({\sigma})=\sum_{\begin{subarray}{c}{\tau}\in X(k)\\\
{\sigma}\subseteq{\tau}\end{subarray}}{{F}({\tau})}$

When it is clear from context the dimension will be omitted.

Much like we used the coboundary operator to define coboundaries and cocycles
we can use the boundary operator to define boundaries and cycles:

######  Definition 7.14 (Cycles and Boundaries).

Define the boundaries to be:

$B_{k}\left(X;\mathbbm{F}_{2}\right)=\operatorname*{Im}\left(\partial_{k+1}\right)$

And the cycles to be:

$Z_{k}\left(X;\mathbbm{F}_{2}\right)=\ker\left(\partial_{k}\right)$

Note that because we take cochains over $\mathbbm{F}_{2}$ we think of a set of
faces and the cochain that sets the value $1$ to members of the set and $0$
otherwise interchangeably.

Note that the $1$-dimensional cycles are sets of edges that “touch” every
vertex an even number of times. We can now define the homology of the complex:

######  Definition 7.15 (Homology).

Define the $k$-dimensional homology of the complex to be:

$H_{k}\left(X;\mathbbm{F}_{2}\right)=Z_{k}\left(X;\mathbbm{F}_{2}\right)/B_{k}\left(X;\mathbbm{F}_{2}\right)$

Generally, the $1$-dimensional homology can be thought of as the
$1$-dimensional “holes” in the complex. We use this notion in order to prove
the following:

######  Lemma 7.16.

There is a member of the homology that is a $1$-non-skipping cycle.

###### Proof.

We will show that any non-empty cycle of minimal size (i.e. that sets the
value $1$ to the minimal number of edges) in the homology of $X$ is a $1$-non-
skipping cycle. Let $\gamma\in Z_{1}\left(X;\mathbbm{F}_{2}\right)$ be a
cycle.

We will first show that the cycle “touches” each vertex exactly twice.
Consider the subgraph induced by the $\gamma$ and note that it has an Euler
cycle. If there is a vertex that the cycle touches more than two times,
consider the euler cycle that begins in that vertex. Note that it can be
divided into cycles - one for every two consecutive visits to that vertex.
Denote these cycles $\gamma^{\prime}_{1},\cdots,\gamma^{\prime}_{k}$. Note
that $\gamma=\sum_{i=1}^{k}{\gamma^{\prime}_{i}}$, therefore there exists $i$
such that $\gamma^{\prime}_{i}\notin B_{1}\left(X;\mathbbm{F}_{2}\right)$
which contradicts the minimality of $\gamma$.

We move on to show that it is $1$-non-skipping Assume that there are $i,j$
such that $i+1<j$ and $\left\\{\gamma_{i},\gamma_{j}\right\\}\in X(1)$.
consider the following cycles:

$\gamma_{1}=\left(\gamma_{0},\cdots,\gamma_{i},\gamma_{j},\cdots\gamma_{n}\right)\qquad\qquad\gamma_{2}=\left(\gamma_{i},\cdots,\gamma_{j},\gamma_{i}\right)$

Note that $\gamma=\gamma_{1}+\gamma_{2}$ and therefore either
$\gamma_{1}\notin B_{1}\left(X;\mathbbm{F}_{2}\right)$ or $\gamma_{2}\notin
B_{1}\left(X;\mathbbm{F}_{2}\right)$. Both, however, are cycles and therefore
either $\gamma_{1}\in H_{1}\left(X;\mathbbm{F}_{2}\right)$ or $\gamma_{2}\in
H_{1}\left(X;\mathbbm{F}_{2}\right)$ which contradicts the minimality of
$\gamma$. ∎

######  Corollary 7.17.

If there is a lower bound on the size of members of the homology then it is
also a lower bound on the number of queries that must be performed in order to
test list agreement without the $2$-differing assumption.

###### Proof.

Combining Lemma 7.16 and Lemma 7.11 proves this corollary. ∎

We note that many complexes of interest have non-vanishing homology. Moreover,
there are cases where the size of members of the homology are bounded from
below by a non-constant bound (see [KT21], for example). This suggests that in
many complexes testing list agreement requires a non-constant number of
queries.

Before we close this subsection it is important to note that while the
homology include $1$-non-skipping cycles it not the case that every
$1$-skipping-cycle is a member of the $1$-dimensional homology. Consider the
following cycle:

######  Example 7.18 (A $1$-non-skipping cycle that is not a member of the
homology).

Consider the following complex:

${v}$$\gamma_{0}$$\gamma_{1}$$\gamma_{2}$$\gamma_{3}$$\gamma_{4}$$\gamma_{5}$$\gamma_{6}$$\gamma_{7}$

Note that the bolded cycle in this complex _is_ a boundary and yet it is
$1$-non-skipping.

###  7.2 Spherical Buildings And List Agreement Testing Without the
$2$-differing Assumption

One useful family of coboundary expanders are the spherical buildings. In this
section we will show a lower bound on the number of queries a list agreement
must perform when the underlying complexes are the spherical buildings. We
will show said lower bound by finding a $1$-non-skipping cycle whose size
increases with the size of the building. Therefore we conclude that there is
no constant query test for list agreement on the spherical buildings. And,
since the spherical buildings have been shown to be both coboundary expanders
and local spectral expanders, show a that the $2$-differing assumption is
_inherent_ for testing list agreement in the domain we consider. We begin by
giving a more detailed description of spherical buildings:

######  Definition 7.19 (Spherical Building).

Let $p$ be a prime number and let $d$ be a dimension. Define the
$d$-dimensional spherical building $\mathbb{S}_{p}^{d}$ to be a simplicial
complex such that:

  * •

Its vertices are the non-trivial subspaces of $\mathbbm{F}_{p}^{d+2}$ (i.e.
subsets that are not $\left\\{0\right\\}$ or $\mathbbm{F}_{p}^{d+2}$).

  * •

Its $d$-dimensional spaces are
${\sigma}=\left\\{{\sigma}_{1},\dots,{\sigma}_{d+1}\right\\}$ such that:

$0<{\sigma}_{1}<\cdots<{\sigma}_{d+1}<\mathbbm{F}_{p}^{d+2}$

We will show the following:

######  Lemma 7.20.

For every prime $p$ there is a $1$-non-skipping cycle of length $2(p-1)$ in
$\mathbb{S}_{p}^{d}$.

We will show that cycle explicitly.

######  Definition 7.21.

For every $i$ define the following subspaces of $\mathbbm{F}^{d}_{p}$ (which
correspond to vertices in): First consider the following vectors:

$v_{i}=\left(1,i,0,0,0,\cdots,0\right)\qquad\qquad
u_{i}=\left(1,0,i,0,0,\cdots,0\right)$

And define the following spaces:

$V_{i}=\operatorname*{span}{\left\\{v_{i}\right\\}}\qquad\qquad
U_{i}=\operatorname*{span}{\left\\{u_{i}\right\\}}\qquad\qquad
W_{i,j}=\operatorname*{span}{\left\\{u_{i},v_{j}\right\\}}$

We will show that the following cycle is $1$-non-skipping:

$\gamma=\left(V_{1},W_{1,1},U_{1},W_{1,2},V_{2},W_{2,2},U_{2},\cdots,U_{p-1},W_{p-1,1},V_{1}\right)$

Note that, by definition, there are no edges between and $V_{i}$ and $U_{j}$.
Therefore all we have to show are the following statements:

  * •

Out of the vertices that combine the cycle, $W_{i,i}$ is only connected to
$V_{i}$ and $U_{i}$.

  * •

Out of the vertices that combine the cycle, $W_{i,i+1}$ is only connected to
$V_{i+1}$ and $U_{i}$.

  * •

Out of the vertices that combine the cycle, $W_{p-1,1}$ is only connected to
$V_{1}$ and $U_{p-1}$.

######  Lemma 7.22.

For every $i\neq j$ it holds that $V_{j}\nsubseteq W_{i,i}$ and
$U_{j}\nsubseteq W_{i,i}$.

###### Proof.

We prove the Lemma using the contra-positive argument: Assume that
$V_{j}\subseteq W_{i,i}$. Therefore there exists $a,b$ such that
$v_{j}=av_{i}+bu_{i}$ and thus:

$\begin{cases}a+b=1\\\ ai=j\\\ bi=0\end{cases}\Rightarrow ai+bi=i\Rightarrow
j+0=i\Rightarrow i=j$

Which contradict our assumption. Similar claims show that $U_{j}\nsubseteq
W_{i,i}$. ∎

######  Lemma 7.23.

For every $i\neq j$ it holds that $V_{j+1}\nsubseteq W_{i,i+1}$ and
$U_{j}\nsubseteq W_{i,i}$.

###### Proof.

We first note that $i\neq 0,p-1$.

Assume that $V_{j+1}\subseteq W_{i,i+1}$. Therefore there exists $a,b$ such
that $v_{j}=av_{i+1}+bu_{i}$ and therefore:

$\begin{cases}a+b=1\\\ a(i+1)=j+1\\\ bi=0\end{cases}\Rightarrow
a(i+1)+b(i+1)=i+1\Rightarrow j+1+b=i+1\Rightarrow\\\ \Rightarrow
b=i-j\Rightarrow(i-j)i=0$

Note that $i\neq j$ and $i\neq 0$ and therefore $V_{j+1}\nsubseteq W_{i,i+1}$.

Similarly assume that $U_{j}\subseteq W_{i,i+1}$. Therefore there exists $a,b$
such that $u_{j}=av_{i+1}+bu_{i}$ and therefore:

$\begin{cases}a+b=1\\\ a(i+1)=0\\\ bi=j\end{cases}\Rightarrow
ai+bi=i\Rightarrow ai+j=i\Rightarrow ai=i-j\Rightarrow\\\ \Rightarrow
i-j+a=0\Rightarrow a=j-i\Rightarrow(j-i)(i+1)=0$

And since $i\neq j$ and $i\neq p-1$ it holds that $U_{j}\nsubseteq W_{i,i+1}$.
∎

######  Lemma 7.24.

Let $i\neq 1$ and $j\neq p-1$ therefore it holds that $V_{i}\nsubseteq
W_{p-1,1}$ and $U_{j}\nsubseteq W_{p-1,1}$.

###### Proof.

Assume that $V_{i}\subseteq W_{p-1,i}$. Therefore there exists $a,b$ such that
$v_{i}=av_{1}+bu_{p-1}$ and therefore:

$\begin{cases}a+b=1\\\ a=i\\\ b(p-1)=0\end{cases}\Rightarrow
b=1-i\Rightarrow(1-i)(p-1)=1\Rightarrow i=1$

Which contradicts our choice of $i$ and thus $V_{i}\nsubseteq W_{p-1,1}$

Likewise assume that $U_{j}\subseteq W_{p-1,i}$. Therefore there exists $a,b$
such that $u_{j}=av_{1}+bu_{p-1}$ and therefore:

$\begin{cases}a+b=1\\\ a=0\\\ b(p-1)=j\end{cases}\Rightarrow b=1\Rightarrow
j=p-1$

Which contradicts our choice of $j$ and thus $U_{j}\nsubseteq W_{p-1,1}$ ∎

We are now ready to prove Lemma 7.20.

###### Proof of Lemma 7.20.

Combining Lemma 7.22, Lemma 7.23 and Lemma 7.24 with the definition of the
spherical buildings proves that $\gamma$ is a $1$-non-skipping cycle. ∎

######  Corollary 7.25.

There is a lower bound of $2(p-1)$ queries that must be performed in order to
test list agreement on $\mathbb{S}_{p}^{d}$.

###### Proof.

Combining Lemma 7.11 and Lemma 7.20 proves this Corollary. ∎

##  8 Testing Direct Sums Using List Agreement Expansion

In this section we will show how to use a $2$-agreement-expander to provide a
test for whether a function is a $k$-direct-sum for any constant $k$. We will
do that by reconstructing an $l$-assignment (with an appropriate choice of
$l$) to each $\left(k+1\right)$-dimensional face and reducing the problem to
list agreement expansion. We start by defining what a direct sums is:

######  Definition 8.1 (Direct sum).

Let $X$ be a $d$-dimensional simplicial complex, $i\leq d$ and let
$F:X(i)\rightarrow\left\\{0,1\right\\}$. We say that $F$ is a $(i+1)$-direct-
sum if there exists a function $f:X(0)\rightarrow\left\\{0,1\right\\}$ such
that:

$\forall{\sigma}\in X(i):F({\sigma})=\sum_{{v}\in{\sigma}}{f({v})}$

We also term $f$ as an origin function of $F$.

In addition we use the following distance function between functions from the
$i$-dimensional faces to $\left\\{0,1\right\\}$:

######  Definition 8.2 (Distance function).

Let $X$ be a $d$-dimensional simplicial complex and let
$F,G:X(i)\rightarrow\left\\{0,1\right\\}$. Define:

$\operatorname{dist}\left(F,G\right)=\sum_{\begin{subarray}{c}{\sigma}\in
X(i)\\\ F({\sigma})\neq
G({\sigma})\end{subarray}}{\operatorname{w}\left({\sigma}\right)}$

Let us present the reconstruction (while noting that in the even case the
reconstruction yields two functions).

######  Lemma 8.3.

If $F$ is a $k$-direct-sum ($k$ is even) and $f$ is an origin function of $F$
then $\mathbbm{1}+f$ is also an origin function of $F$.

###### Proof.

Let ${\sigma}\in X(k-1)$. Consider:

$F({\sigma})=\sum_{{v}\in{\sigma}}{f({v})}=\binom{k}{1}1+\sum_{{v}\in{\sigma}}{f({v})}=\sum_{{v}\in{\sigma}}{1+f({v})}=\sum_{{v}\in{\sigma}}{(\mathbbm{1}+f)({v})}$

∎

######  Lemma 8.4 (Reconstructing a $k$-direct-sum).

Let $F$ be a $k$-direct-sum and then for every face ${\sigma}\in X(k+1)$ one
can reconstruct two possible origin functions if $k$ is even and a single
origin function if $k$ is odd. Note that the $\left|{\sigma}\right|=k+2$, this
is important as one cannot reconstruct the origin function of a $k$-direct sum
using a face whose size is $k+1$.

###### Proof.

We will show that if $k$ is odd then the following algorithm returns a
candidate for an origin function of $F$:

1 for  _every vertex ${v}$_ do

2 pick  _a $k$-dimensional face ${\sigma}$ that includes ${v}$_

3 Set
$f({v})=\sum_{{a}\in\binom{{\sigma}\setminus\left\\{{v}\right\\}}{k-1}}{F(a\cup\left\\{{v}\right\\})}$

4

5 return _$f$_

6 end for

Algorithm 5 reconstruct origin function for odd values of $k$

We will now show that this is indeed an origin function of $F$, if $F$ is a
$k$-direct-sum then it has an origin function (denoted by $f^{\prime}$).
Consider the following:

$\displaystyle\forall{\tau}\in
X(k):f({u})=\sum_{{a}\in\binom{{\tau}\setminus\left\\{{u}\right\\}}{k-1}}{F(a\cup\left\\{{u}\right\\})}=\sum_{{a}\in\binom{{\tau}\setminus\left\\{{u}\right\\}}{k-1}}{\left(f^{\prime}({u})+\sum_{{v}^{\prime}\in{a}}{f^{\prime}({v}^{\prime})}\right)}=$
$\displaystyle\quad\binom{k}{k-1}f^{\prime}({u})+\sum_{v^{\prime}\in
q}{\binom{k-1}{k-2}f^{\prime}(v^{\prime})}=k\cdot
f^{\prime}({u})+\sum_{{v}^{\prime}\in
q}{(k-1)f^{\prime}({v}^{\prime})}=f^{\prime}({u})$

Therefore $f$ is an origin function of $F$.
In the even case, we will show that the following algorithm reconstruct two
options for an origin function of $F$:

1 pick  _${v}\in X(0)$_

2 Define $f_{0},f_{1}$ to be local origin functions of $F$ and set
$f_{0}({v})=0$ and $f_{1}({v})=1$.

3 for  _every other vertex ${v}^{\prime}\neq{v}$ set_ do

4 pick  _a $k$-dimensional face ${\sigma}$ that includes both ${v}$ and
${v}^{\prime}$_

5 Set
$f_{0}({v}^{\prime})=\sum_{{a}\in\binom{{\sigma}\setminus\left\\{{v},{v}^{\prime}\right\\}}{k-2}}{F(a\cup\left\\{{v},{v}^{\prime}\right\\})}$

6 Set $f_{1}({v}^{\prime})=1+f_{0}({v}^{\prime})$

7

8

9 end for

10 return _$f_{0}$ and $f_{1}$_

11

Algorithm 6 reconstruct origin functions for even values of $k$

The proof that these are indeed origin functions of $F$ follows the proof of
the odd case - $F$ is a direct sum therefore it has an origin function
$f^{\prime}$ (assume WLOG that $f^{\prime}({v})=0$):

$\displaystyle\forall{\tau}\in
X(k):f_{0}({u})=\sum_{{a}\in\binom{{\tau}\setminus\left\\{{v},{u}\right\\}}{k-2}}{F(a\cup\left\\{{v},{u}\right\\})}=\sum_{{a}\in\binom{{\tau}\setminus\left\\{{v},{u}\right\\}}{k-2}}{\left(f^{\prime}({v})+f^{\prime}({u})+\sum_{{v}^{\prime}\in{a}}{f^{\prime}({v}^{\prime})}\right)}=$
$\displaystyle\quad\binom{k-1}{k-2}f^{\prime}({u})+\sum_{v^{\prime}\in
q}{\binom{k-2}{k-3}f^{\prime}(v^{\prime})}=\left(k-1\right)f^{\prime}({u})+\sum_{{v}^{\prime}\in
q}{(k-2)\cdot f^{\prime}({v}^{\prime})}=f^{\prime}({u})$

∎

######  Corollary 8.5.

If $F$ is a $k$-direct-sum then:

  * •

If $k$ is odd then it has a single origin function.

  * •

If $k$ is even then it has two origin functions $f_{0}$ and $f_{1}$ such that
$f_{0}=\mathbbm{1}+f_{1}$.

###### Proof.

The proof of this corollary follows exactly the steps shown in Lemma 8.4. ∎

######  Note.

Regardless of the parity of $k$ the resulting $l$-assignment is locally
differing (either trivially since in case that $l=1$ or non trivially since
$f_{0}=\mathbbm{1}+f_{1}$).

Before we move on to describe the test let us first show how to query the
origin functions using $k$-dimensional faces:

######  Corollary 8.6.

If $F$ is a $k$-direct-sum then:

  * •

If $k$ is odd then every choice of ${\sigma}$ in algorithm 5 results in the
same function $f$.

  * •

If $k$ is even then any pick of ${v}$ and ${\sigma}$ in algorithm 6 results in
either $f_{0}$ or $f_{1}$.

###### Proof.

In Lemma 8.4 it is shown that if $F$ is a $k$-direct-sum then when running the
algorithm corresponding to the value of $k$ is an origin function of $F$.
Therefore using Corollary 8.5 these are indeed the desired functions. ∎

######  Corollary 8.7.

If $F$ is a $k$-direct-sum then for every ${\tau}\in X(k)$:

  * •

If $k$ is odd one can query the values of $f$ on a face ${\tau}$ using $k+1$
queries.

  * •

If $k$ is even one can query the values of $f_{0},f_{1}$ on a face ${\tau}$
using $k+1$ queries.

###### Proof.

For the odd case run step 3 of Algorithm 5 with ${\sigma}={\tau}$. For even
values of $k$ pick a vertex ${u}$ and set the value of $f_{0}({u})=0$ and
$f_{1}({u})=1$ and then run steps 6-6 of algorithm 6 with ${v}={u}$ and
${\sigma}={\tau}$. Corollary 8.6 guarantees that these local assignments are
indeed $f$ or $f_{0}$ and $f_{1}$ in the odd or even case respectively. ∎

Consider the following test for $k$-direct-sum:

Run the test for $l$-agreement on the $k$-dimensional faces (where $l=1$ if
$k$ is odd and $l=2$ if $k$ is even) when querying the local assignment,
calculate the origin function(s) using the algorithm described in Corollary
8.7.

Algorithm 7 $k$-direct-sum

We will show that this tests whether $F$ is a $k$-direct-sum.

######  Lemma 8.8.

If $F$ is a $k$-direct-sum then it passes the test posed in Algorithm 7 with
probability $1$.

###### Proof.

If $k$ is odd then $f$ is an origin function of $F$ due to Lemma 8.4 therefore
${\mathcal{{F}}}=\left\\{f|_{v}\right\\}_{{v}\in X(k)}$ is the assignment
tested which is indeed an agreeing assignment.
If $k$ is even then $f_{0}$ and $f_{1}$ are origin functions of $F$ therefore
the assignment calculated by Corollary 8.7 (denoted ${\mathscr{{F}}}$)
satisfied that either ${\mathscr{{F}}}_{i}^{\sigma}=f_{i}|_{v}$ or
${\mathscr{{F}}}_{i}^{\sigma}=f_{1-i}|_{\sigma}$. It is easy to see that
${\mathscr{{F}}}$ is an agreeing $2$-assignment and the test always accepts. ∎

######  Lemma 8.9.

Let $F:X(k-1)\rightarrow\left\\{0,1\right\\}$ be a cochain and let
${\mathscr{{F}}}$ be the $l$-assignment calculated in Corollary 8.7 then:

$\operatorname{dist}{(F,k\text{-direct-
sums})}\leq\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}$

###### Proof.

Let ${\mathscr{{G}}}$ be the agreeing $k$-dimensional $l$-assignment closest
to ${\mathscr{{F}}}$. ${\mathscr{{G}}}$ is an agreeing $l$-assignment and
therefore for every ${\sigma}\in X(k)$ there exists a permutation
$\pi_{\sigma}$ such that for all $i\in[l]$:
${\mathcal{{G}}}_{i}^{\sigma}={\mathscr{{G}}}^{\sigma}_{\pi_{\sigma}(i)}$ is
an agreeing assignment. Let ${\mathcal{{F}}}_{i}$ be the assignment
${\mathcal{{F}}}_{i}^{\sigma}={\mathscr{{F}}}_{\pi_{\sigma}(i)}^{\sigma}$.
Also let ${\mathcal{{G}}}$ be the assignment ${\mathcal{{G}}}_{\tilde{i}}$
such that
$\tilde{i}=\operatorname*{arg\,min}_{i}{\left\\{\operatorname{dist}{({\mathcal{{G}}}_{i},{\mathcal{{F}}}_{i})}\right\\}}$.
Consider $G({\sigma})=\sum_{{v}\in{\sigma}}{{\mathcal{{G}}}({v})}$. It is easy
to see that $G$ is a $k$-direct-sum therefore all we have left is to find the
distance between $F$ and $G$.

$\displaystyle\operatorname{dist}{(F,G)}$
$\displaystyle=\left\|\left\\{{\sigma}\in X(k-1)\middle|F({\sigma})\neq
G({\sigma})\right\\}\right\|\leq\left\|\operatorname{\Gamma}^{k}\left(\left\\{{\sigma}\in
X(k-1)\middle|F({\sigma})\neq G({\sigma})\right\\}\right)\right\|$
$\displaystyle=\left\|\left\\{{\tau}\in
X(k)\middle|\exists{\sigma}\in\binom{{\tau}}{k}:F({\sigma})\neq
G({\sigma})\right\\}\right\|=\left\|\left\\{{\tau}\in
X(k)\middle|\exists{\sigma}\in\binom{{\tau}}{k}:{\mathcal{{F}}}_{\tilde{i}}^{\sigma}\neq{\mathcal{{G}}}^{\sigma}\right\\}\right\|$
$\displaystyle=\operatorname{dist}{({\mathcal{{F}}}_{\tilde{i}},{\mathcal{{G}}})}=\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}{({\mathcal{{F}}}_{\tilde{i}},{\mathcal{{G}}})}}\leq\frac{1}{l}\sum_{i=1}^{l}{\operatorname{dist}{({\mathcal{{F}}}_{i},{\mathcal{{G}}}_{i})}}=\operatorname{dist}{({\mathscr{{F}}},{\boldsymbol{{\mathscr{{A}}}}})}$

∎

######  Theorem 8.10.

Any simplicial complex that is a $\gamma$-list agreement expansion supports a
$\left(3\left(k+1\right),\gamma\right)$-test for $k$-direct-sums.

###### Proof.

Note that combing Corollary 8.7, Lemma 8.8 and Lemma 8.9 yields a
$\left(3\left(k+1\right),\gamma\right)$-test for $k$-direct-sums. ∎

## References

  * [BKS18] Boaz Barak, Pravesh K Kothari, and David Steurer.  Small-set expansion in shortcode graph and the 2-to-2 conjecture.  arXiv preprint arXiv:1804.08662, 2018.
  * [DD19] Yotam Dikstein and Irit Dinur.  Agreement testing theorems on layered set systems.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1495–1524. IEEE, 2019.
  * [DDFH18] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Boolean functions on high-dimensional expanders.  arXiv preprint arXiv:1804.08155, 2018.
  * [DDG+17] Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, and Igor Shinkar.  Direct sum testing.  SIAM Journal on Computing, 46(4):1336–1369, 2017.
  * [DDHRZ20] Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi.  Locally testable codes via high-dimensional expanders.  arXiv preprint arXiv:2005.01045, 2020.
  * [DFH17] Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Agreement tests on graphs and hypergraphs.  arXiv preprint arXiv:1711.09426, 2017.
  * [DFH19] Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Analyzing boolean functions on the biased hypercube via higher-dimensional agreement tests.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2124–2133. SIAM, 2019.
  * [DHKRZ18] Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi.  From local to robust testing via agreement testing.  In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [DK17] Irit Dinur and Tali Kaufman.  High dimensional expanders imply agreement expanders.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 974–985. IEEE, 2017.
  * [DKK+18] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  Towards a proof of the 2-to-1 games conjecture?  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 376–389, 2018.
  * [DM19] Irit Dinur and Roy Meshulam.  Near coverings and cosystolic expansion–an example of topological property testing.  arXiv preprint arXiv:1909.08507, 2019.
  * [GK19] Roy Gotlib and Tali Kaufman.  Testing odd direct sums using high dimensional expanders.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [Gro10] Mikhail Gromov.  Singularities, expanders and topology of maps. part 2: From combinatorics to topology via algebraic isoperimetry.  Geometric and Functional Analysis, 20(2):416–526, 2010.
  * [IJK09] Russell Impagliazzo, Ragesh Jaiswal, and Valentine Kabanets.  Approximate list-decoding of direct product codes and uniform hardness amplification.  SIAM Journal on Computing, 39(2):564–605, 2009.
  * [KL14] Tali Kaufman and Alexander Lubotzky.  High dimensional expanders and property testing.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 501–506, 2014.
  * [KM20] Tali Kaufman and David Mass.  Local-to-global agreement expansion via the variance method.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
  * [KM21] Tali Kaufman and David Mass.  Unique-neighbor-like expansion and group-independent cosystolic expansion.  In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [KMS17] Subhash Khot, Dor Minzer, and Muli Safra.  On independent sets, 2-to-2 games, and grassmann graphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 576–589, 2017.
  * [KT21] Tali Kaufman and Ran J. Tessler.  New cosystolic expanders from tensors imply explicit quantum LDPC codes with $\Omega$($\surd$_n_ log${}^{\mbox{\emph{k}}}$ _n_) distance.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 1317–1329. ACM, 2021.
  * [LM06] Nathan Linial and Roy Meshulam.  Homological connectivity of random 2-complexes.  Combinatorica, 26(4):475–487, 2006.
  * [Sur84] David B Surowski.  Covers of simplicial complexes and applications to geometry.  Geometriae Dedicata, 16(1):35–62, 1984.
  * [Yao82] Andrew C. Yao.  Theory and application of trapdoor functions.  In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 80–91, 1982.

##  Appendix A On the Testability of Coboundaries in the Representation
Complex

In this section we will show how test the coboundaries from the cochains in
the representation complex. It is important to note that the representation
complexes are expanding but their cohomology is not trivial. Before presenting
the test we have to define a $\left(k-1\right)$-empty-triangle:

######  Definition A.1 ($\left(k-1\right)$-empty-triangle).

Let $X$ be a simplicial complex and let $\hat{R}^{k}(X)$ be its
$k$-dimension’s representation complex. Define a $\left(k-1\right)$-empty-
triangle in $\hat{R}^{k}(X)$ to be a set of vertices $\left\\{u,v,w\right\\}$
such that all there is an edge connecting every pair of them and
$\left\\{u\cap v,v\cap w,w\cap u\right\\}\in\hat{R}^{k-1}(X)(2)$ (with some
orientation). Denote the set of $\left(k-1\right)$-empty-triangles by
$\hat{R}^{k}(X)(\triangle)$. When the dimension is clear from context we will
omit it.

Consider the following test:

1 pick  _with probability 0.5._

2 Pick a triangle $(u,v,w)$ with respect to the norm of $\hat{R}^{k}(X)$.

3 Pick a $\left(k-1\right)$-empty-triangle $(u,v,w)$ with respect to the norm
of $\hat{R}^{k-1}(X)$.

4

return whether ${F}(u,v){F}(v,w){F}(w,u)=1$181818Note that ${F}$ is only
defined on edges from $\hat{R}^{k}(X)$ and not $\hat{R}^{k-1}(X)$..

Algorithm 8 Empty Triangle Test

We will show that the empty triangle test is a property test for whether the
cochain $f$ is a coboundary. As previously stated, it is known that the
representation complex is expanding (i.e. given an oracle access to a cochain
${F}$ one can test the distance of ${F}$ from the cocycles). Therefore we
would like to differentiate between coboundaries and non-trivial cohomology
components. In order to do so, it would be useful to examine the structure of
cocycles in the representation complex. Specifically we will use the fact that
the original complex’s links are coboundary expanders in order to claim that a
cocycle in the representation complex is a coboundary around every core.

######  Lemma A.2.

Let ${F}\in Z^{1}\left(\hat{R}^{k}(X);G\right)$ then for every $c\in X(k-1)$
it holds that ${F}|_{\hat{R}^{k}_{c}(X)}\in B^{1}\left(\hat{R}^{k}(X)\right)$.

###### Proof.

Since ${F}\in Z^{1}\left(\hat{R}^{k}(X);G\right)$ it holds that for every
$(u,v,w)\in\hat{R}^{k}(X)(2)$ it holds that
${F}(u,v){F}(v,w){F}(w,u)=1$. Therefore for every
$(u,v,w)\in\hat{R}^{k}_{c}(X)(2)$ the same holds. Consequently
${F}|_{\hat{R}^{k}_{c}(X)}$ is a cocycle in $\hat{R}^{k}_{c}(X)\cong X_{c}$.
The lemma holds since every cocycle in $X_{c}$ is a coboundary (due to the
fact that $X_{c}$ is a coboundary expander). ∎

We use this lemma in order to conclude that the only way in which cocycles
differ from each other is by how the coboundaries of different cores are
“attached” to one another. In the next section we will define that notion more
precisely and investigate the properties of different of such an attachment.

###  A.1 The Attachment Map

In order to discuss the ways coboundaries around cores are attached to one
another we define the following attachment map:

######  Definition A.3 (Attachment maps).

Let ${F}\in Z^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ be a cocycle in $X$ and
let
$\left\\{h^{c}\right\\}_{c\in X(k-1)}$ be functions such that:

  * •

$h^{c}:c\rightarrow S_{l}$

  * •

$\forall c\in X(k-1):{F}|_{\hat{R}^{k}_{c}(X)}=d_{0}h^{c}$.

Define the attachment map of ${F}$ according to $\left\\{h^{c}\right\\}$
denoted by ${\check{F}}_{\left\\{h^{c}\right\\}}\in
C^{1}\left(\hat{R}^{k-1}(X)\right)$ to be:

${\check{F}}_{\left\\{h^{c}\right\\}}(\check{u},\check{v})=\left(h^{\check{u}}\left(\check{u}\cup\check{v}\right)\right)^{-1}h^{\check{v}}\left(\check{u}\cup\check{v}\right)$

We will begin by showing a connection between the distance of an attachment
map of ${F}$ from being a cocycle and the distance of ${F}$ from being a
coboundary. Then, in subsection A.4, we will show how to use this in order to
show that the empty triangle test is indeed a test for the coboundaries in the
representation complex. But before we do that let us first show that the
distance between the attachment map and the coboundaries is invariant of the
choice of local coboundaries. In order to do that we will begin by
characterizing the different choices of functions $h$ such that
${F}|_{\hat{R}^{k}_{c}(X)}=d_{0}h$:

######  Lemma A.4.

Let $X$ be a simplicial complex such that the graph $(X(0),X(1))$ is connected
and let $h_{1},h_{2}\in C^{0}\left(X;S_{l}\right)$ such that
${F}=d_{0}h_{1}=d_{0}h_{2}$ then there exists $\sigma\in S_{l}$ such that
$h_{1}(u)=h_{2}(u)\sigma$.

###### Proof.

Let $u_{0}\in X(0)$ be a vertex. Also let
$\sigma=h_{2}^{-1}(u_{0})h_{1}(u_{0})$ and note that
$h_{1}(u_{0})=h_{2}(u_{0})\sigma$. For every vertex $u\in X(0)$ pick a path
$\gamma=(u,u_{n-1},\dots,u_{0})$ between $u$ and $u_{0}$ and consider:

$h_{1}(u)h_{1}^{-1}(u_{0})={F}(u,u_{n-1}){F}(u_{n-1},u_{n-2})\cdots{F}(u_{1},u_{0})=h_{2}(u)h_{2}^{-1}(u_{0})$

And therefore:

$h_{1}(u)=h_{2}(u)h_{2}^{-1}(u_{0})h_{1}^{-1}(u_{0})=h_{2}(u)\sigma$

∎

We are now ready to prove the invariance of the distance to the choice of
functions $h$:

######  Lemma A.5.

Let $\left\\{h^{c}_{1}\right\\}_{c\in X(k-1)}$ and
$\left\\{h^{c}_{2}\right\\}_{c\in X(k-1)}$ be two choices of functions such
that ${F}(u,v)=h^{u\cap v}_{1}(u)\left(h^{u\cap v}_{1}(u)\right)^{-1}=h^{u\cap
v}_{2}(u)\left(h^{u\cap v}_{2}(u)\right)^{-1}$. Then:

$\operatorname{dist}\left({\check{F}}_{h_{1}},B^{1}\left(\hat{R}^{k-1}(X);S_{l}\right)\right)=\operatorname{dist}\left({\check{F}}_{h_{2}},B^{1}\left(\hat{R}^{k-1}(X);S_{l}\right)\right)$

###### Proof.

Let
$\epsilon=\operatorname{dist}\left({\check{F}}_{h_{1}},B^{1}\left(\hat{R}^{k-1}(X);S_{l}\right)\right)$
therefore there exists $\varphi_{h_{1}},\psi_{h_{1}}$ such that
$\varphi_{h_{1}}$ is a coboundary, $\left\|\psi_{h_{1}}\right\|=\epsilon$, and
$\varphi_{h_{1}}={\check{F}}_{h_{1}}\psi_{h_{1}}^{-1}$. Let $\phi_{h_{1}}$ be
a cochain such that $\varphi_{h_{1}}=d_{0}\phi_{h_{1}}$. Note that around
every core the complex is connected191919Due to the fact that the links of $X$
are coboundary expanders their $0$-cohomology is trivial and therefore the
complex is connected. therefore due to Lemma A.4 it holds that:

$\forall c\in X(k-1)\exists{\sigma}_{c}:h_{2}^{c}(u)=h_{1}^{c}(u){\sigma}_{c}$

Therefore:

${\check{F}}_{h_{2}}(\check{u},\check{v})=\sigma_{\check{u}}^{-1}\left(h_{1}^{\check{u}}(\check{u}\cup\check{v})\right)^{-1}h_{1}^{\check{v}}(\check{u}\cup\check{v})\sigma_{\check{v}}$

Now, consider
$\phi_{h_{2}}(\check{u})=\sigma_{\check{u}}^{-1}\phi_{h_{1}}(\check{u})$ and:

$\varphi_{h_{2}}(\check{u},\check{v})=d_{0}\phi_{h_{2}}(\check{u},\check{v})=\sigma_{\check{u}}^{-1}\phi_{h_{1}}(\check{u})\phi_{h_{1}}^{-1}(\check{v})\sigma_{\check{v}}$

We will conclude the proof by sowing that
$\operatorname{dist}({F}_{h_{1}},\varphi_{h_{1}})=\operatorname{dist}({F}_{h_{2}},\varphi_{h_{2}})$:

$\displaystyle\varphi_{h_{2}}(\check{u},\check{v})={\check{F}}_{h_{2}}(\check{u},\check{v})$
$\displaystyle\Leftrightarrow\sigma_{\check{u}}^{-1}\phi_{h_{1}}(\check{u})\phi_{h_{1}}^{-1}(\check{v})\sigma_{\check{v}}=\sigma_{\check{u}}^{-1}\left(h_{1}^{\check{u}}(\check{u}\cup\check{v})\right)^{-1}h_{1}^{\check{v}}(\check{u}\cup\check{v})\sigma_{\check{v}}\Leftrightarrow$
$\displaystyle\Leftrightarrow\phi_{h_{1}}(\check{u})\phi_{h_{1}}^{-1}(\check{v})=\left(h_{1}^{\check{u}}(\check{u}\cup\check{v})\right)^{-1}h_{1}^{\check{v}}(\check{u}\cup\check{v})\Leftrightarrow\varphi_{h_{1}}(\check{u},\check{v})={\check{F}}_{h_{1}}(\check{u},\check{v})$

∎

Due to the invariance of the choice of functions $h$ whenever we refer to the
attachment map of a cocycle ${F}$ we would consider any cocycle and will omit
the choice of $h$ from the notation. We will now show a connection between the
distance of attachments maps from the coboundaries and the distance of a
cocycle from the coboundaries:

######  Lemma A.6.

Let ${F}\in Z^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ be a cocycle in
$\hat{R}^{k}(X)$ such that ${\check{F}}$ is $\epsilon$-far from being a
coboundary, i.e. there exists $\varphi$ and $\psi$ such that
$\left\|\psi\right\|\leq\epsilon$, $\varphi=d_{0}\widetilde{g}$ is a
coboundary and $\varphi={\check{F}}\psi^{-1}$. In addition for every vertex
$u$ let $c_{u}$ be a core of $u$ (which we will refer to as the canonical core
of $c$). Consider $g(u)=h^{c_{u}}(u)\widetilde{g}(c_{u})$ and
${\widetilde{F}}=d_{0}g$ then:

$\operatorname{dist}\left({F},{\widetilde{F}}\right)=\left\|\left\\{(u,v)\in\hat{R}^{k}(X)(1)\middle|\psi(c_{u},u\cap
v)=\left(\varphi(c_{v},u\cap v)\right)^{-1}\psi(c_{v},u\cap
v)\varphi(c_{v},u\cap v)\right\\}\right\|$

###### Proof.

Note that:

${\widetilde{F}}=h^{c_{u}}(u)\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\left(h^{c_{v}}(v)\right)^{-1}$

Now, consider when ${F}\neq{\widetilde{F}}$:

$\displaystyle{F}\neq{\widetilde{F}}\Leftrightarrow$ $\displaystyle h^{u\cap
v}(u)\left(h^{u\cap v}(v)\right)^{-1}\neq
h^{c_{u}}(u)\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\left(h^{c_{v}}(v)\right)^{-1}\Leftrightarrow$
$\displaystyle\left(h^{c_{u}}(u)\right)^{-1}h^{u\cap v}(u)\left(h^{u\cap
v}(v)\right)^{-1}h^{c_{v}}(v)\neq\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\Leftrightarrow$
$\displaystyle{\check{F}}(c_{u},u\cap v){\check{F}}(u\cap
v,c_{v})\neq\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\Leftrightarrow$
$\displaystyle\varphi(c_{u},u\cap v)\psi(c_{u},u\cap v)\varphi(u\cap
v,c_{v})\psi(u\cap
v,c_{v})\neq\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\Leftrightarrow$
$\displaystyle\widetilde{g}(c_{u})\left(\widetilde{g}(u\cap
v)\right)^{-1}\psi(c_{u},u\cap v)\varphi(u\cap v,c_{v})\psi(u\cap
v,c_{v})\neq\widetilde{g}(c_{u})\left(\widetilde{g}(c_{v})\right)^{-1}\Leftrightarrow$
$\displaystyle\varphi(c_{v},u\cap v)\psi(c_{u},u\cap v)\varphi(u\cap
v,c_{v})\psi(u\cap v,c_{v})\neq 1\Leftrightarrow$
$\displaystyle\psi(c_{u},u\cap v)=\left(\varphi(c_{v},u\cap
v)\right)^{-1}\psi(c_{v},u\cap v)\varphi(c_{v},u\cap v)$

∎

We are going to bound $\operatorname{dist}({F},{\widetilde{F}})$ using the
stronger condition presented in the following corollary

######  Corollary A.7.

Let ${F},{\widetilde{F}},\psi$ as in Lemma A.6. If
${F}(u,v)\neq{\widetilde{F}}(u,v)$ then either $\psi(c_{u},u\cap v)\neq 1$ or
$\psi(c_{v},u\cap v)\neq 1$ (or both).

###### Proof.

If $\psi(c_{u},u\cap v)=\psi(c_{v},u\cap v)=1$ then:

$\psi(c_{u},u\cap v)=\left(\varphi(c_{v},u\cap v)\right)^{-1}\psi(c_{v},u\cap
v)\varphi(c_{v},u\cap v)\Leftrightarrow\left(\varphi(c_{v},u\cap
v)\right)^{-1}\varphi(c_{v},u\cap v)=1$

Since by definition $\left(\varphi(c_{v},u\cap
v)\right)^{-1}\varphi(c_{v},u\cap v)=1$ it holds that
${F}(u,v)={\widetilde{F}}(u,v)$. ∎

We will now move on to show that the
$\operatorname{dist}\left({F},{\widetilde{F}}\right)$ can be bound from above
by $\left\|\psi\right\|$. Before we are able to do that, however, we have to
first understand the structure of the empty triangles (which we explore in
subsection A.2) as well as further explore the connection between a cocycle
and its attachment maps (which we explore in subsection A.3).

###  A.2 On the $\left(k-1\right)$-empty-triangles

In this section we will discuss the structure of the $\left(k-1\right)$-empty-
triangles in the $k$-dimensional representation complex. Let us begin by
describing the $\left(k-1\right)$-empty-triangles:

######  Lemma A.8.

Let $(u,v)\in\hat{R}^{k}(X)(1)$ and for any choice of $A\in\binom{u\cap
v}{k-1}$ let $w=\left(u\triangle v\right)\cup A$ then $\left\\{u,v,w\right\\}$
is a $\left(k-1\right)$-empty-triangle.

###### Proof.

We will first prove that all the edges of the $\left(k-1\right)$-empty-
triangle exist. We will show WLOG that $\left|u\cap w\right|=k$:

$\left|u\cap w\right|=\left|u\cap\left(\left(u\triangle v\right)\cup
A\right)\right|=\left|\left(u\cap\left(u\triangle
v\right)\right)\cup\left(u\cap A\right)\right|=\left|u\cap\left(u\triangle
v\right)\right|+\left|u\cap A\right|=1+k-1=k$

All we have left to prove is that $\left\\{u\cap v,v\cap w,w\cap
u\right\\}\in\hat{R}^{k-1}(X)(2)$. Note that the intersection between any pair
of vertices out of $\left\\{u\cap v,v\cap w,w\cap u\right\\}$ is the same and
equals to $u\cap v\cap w$. Therefore all we have to prove is that
$\left|\left\\{u\cap v,v\cap w,w\cap u\right\\}\right|=k-1$ and that
$\left(u\cap v\right)\cup\left(v\cap w\right)\cup\left(w\cap u\right)\in
X(k+1)$ in order to prove the lemma. Consider the following:

$\left|\left(u\cap v\right)\cap\left(v\cap w\right)\right|=\left|u\cap v\cap
w\right|=\left|A\right|=k-1$

Finally note that:

$\displaystyle\left(u\cap v\right)\cup\left(v\cap w\right)\cup\left(w\cap
u\right)$ $\displaystyle=\left(u\cap v\right)\cup\left(\left(v\setminus
u\right)\cup A\right)\cup\left(\left(u\setminus v\right)\cup A\right)=$
$\displaystyle=\left(u\cap v\right)\cup\left(v\setminus
u\right)\cup\left(u\setminus v\right)=u\cup v\in X(k+1)$

And therefore $w$ forms an empty triangle with $u,v$. ∎

######  Lemma A.9.

Let $w\in\hat{R}^{k}(X)(0)$. If there exist $u,v\in\hat{R}^{k}(X)(0)$ such
that $\left\\{w,u,v\right\\}$ is an empty triangle in $\hat{R}^{k}(X)$ then
there exists $A\in\binom{u\cap v}{k-1}$ such that $w=\left(u\triangle
v\right)\cup A$

###### Proof.

First note that $\left\\{w,u,v\right\\}$ is an empty triangle and therefore:

$k-1=\left|\left(u\cap v\right)\cap\left(v\cap w\right)\cap\left(w\cap
u\right)\right|=\left|u\cap v\cap w\right|$

Let $A=u\cap v\cap w$. We will now prove that $w=\left(u\triangle v\right)\cup
A$: let $a\in\left(u\triangle v\right)\cup A$. If $a\in A$ then $a\in w$.
Otherwise $a\in u\triangle v$, assume WLOG that $a\in u$. If $a\notin w$ then
$w=\left(u\cup v\right)\setminus\left\\{a\right\\}=v$ which contradicts the
fact that $w\neq v$. Therefore $w\subseteq\left(u\triangle v\right)\cup A$. We
will finish the proof by showing that both sets are of the same cardinality:

$\left|\left(u\triangle v\right)\cup A\right|=\left|\left(u\triangle
v\right)\right|+\left|A\right|=2+k-1=k+1=\left|w\right|$

∎

Now that we understand the structure of the empty triangles we can consider
how many empty triangles are supported by a single edge in $\hat{R}^{k}(X)$:

######  Lemma A.10.

Evey edge $(u,v)\in\hat{R}^{k}(X)(1)$ supports exactly $k$ empty triangles.

###### Proof.

This is immediate from Lemma A.8 and Lemma A.9: Due to Lemma A.8 there exists
at least $k$ empty triangles supported by $(u,v)$ and due to Lemma A.9 there
cannot be more then $k$ vertices that form an empty triangle with $(u,v)$
(note that this is because there are exactly $k$ different choices of $A$). ∎

We are now ready to explore the connections between the empty triangles of
$\hat{R}^{k}(X)$ and the triangles of $\hat{R}^{k-1}(X)$:

######  Lemma A.11.

Let $(u,v)\in\hat{R}^{k}(X)(1)$ and let $w\in\hat{R}^{k}(X)(0)$ such that
$\left\\{u,v,w\right\\}$ is an empty triangle then:

$\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u\cap
v,v\cap w,w\cap u)\right)}=\frac{k}{3}$

###### Proof.

Note that:

$\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)=\frac{1}{\binom{k+2}{k}}\operatorname{w}_{X}\left(u\cup
v\right)$

In addition note that:

$\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u\cap v,v\cap w,w\cap
u)\right)=\frac{1}{\binom{k+2}{k+1}}\operatorname{w}_{X}\left(u\cup v\right)$

Both due to Lemma 3.12 therefore:

$\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u\cap
v,v\cap w,w\cap
u)\right)}=\frac{\frac{1}{\binom{k+2}{k}}\operatorname{w}_{X}\left(u\cup
v\right)}{\frac{1}{\binom{k+2}{k+1}}\operatorname{w}_{X}\left(u\cup
v\right)}=\frac{\binom{k+2}{k+1}}{\binom{k+2}{k}}=\frac{k}{3}$

∎

######  Corollary A.12.

The weight of all the empty triangles supported by a single edge
$(u,v)\in\hat{R}^{k}(X)$ satisfies:

$\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{\sum_{\begin{subarray}{c}w\in\hat{R}^{k}(X)(0)\\\
\left\\{u,v,w\right\\}\in\hat{R}^{k}(X)(\triangle)\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((u\cap
v,v\cap w,w\cap u)\right)}}=\frac{1}{3}$

###### Proof.

Note that, due to Lemma A.10 there are exactly $k$ possible options for $w$,
denote them $w_{1},\dots,w_{k}$. Now consider:

$\displaystyle\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{\sum_{\begin{subarray}{c}w\in\hat{R}^{k}(X)(0)\\\
\left\\{u,v,w\right\\}\in\hat{R}^{k}(X)(\triangle)\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((u\cap
v,v\cap w,w\cap
u)\right)}}=\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{\sum_{i=1}^{k}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((u\cap
v,v\cap w_{i},w_{i}\cap u)\right)}}=$
$\displaystyle\quad=\frac{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,v)\right)}{k\cdot\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u\cap
v,v\cap w,w\cap u)\right)}=\frac{k}{3k}=\frac{1}{3}$

∎

Now that we have further explored the connection between the edges of
$\hat{R}^{k}(X)$ and the triangles of $\hat{R}^{k-1}(X)$ we are ready to
explore the connection between a cochain and its attachment maps.

###  A.3 On the Connection Between a Cocycle and Its Attachment Map

We are now ready to further explore the connection between a cocycle and its
attachment maps. Before we do that, however, it would be useful to define a
version of the $1$-faces that are not oriented:

######  Definition A.13.

Let $X$ be a simplicial complex. Define the non-oriented set of $1$-faces to
be:

$X(1)^{+}=\left\\{(u,v)\middle|(u,v)\in X(1)\text{ or }(v,u)\in X(1)\right\\}$

In addition, we would consider the weight of both $(u,v)$ and $(v,u)$ to be
the same.

Let us now describe another connection between the $1$-faces of
$\hat{R}^{k-1}(X)$ and $\hat{R}^{k}(X)$:

######  Lemma A.14.

Let $u\in\hat{R}^{k}(X)(0)$ and let $c_{u},\check{v}$ be two cores that are
contained in $u$. Then:

$\operatorname{w}_{\hat{R}^{k-1}(X)}\left((c_{u},\check{v})\right)=\frac{1}{k}\sum_{\begin{subarray}{c}(u,u^{\prime})\in\hat{R}^{k}(X)(1)^{+}\\\
u\cap
u^{\prime}=\check{v}\end{subarray}}{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,u^{\prime})\right)}$

###### Proof.

Consider the weight of $(c_{u},\check{v})$:

$\operatorname{w}_{\hat{R}^{k-1}(X)}\left((c_{u},\check{v})\right)=\frac{1}{\binom{k+1}{k-1}}\operatorname{w}_{X}\left(c_{u}\cup\check{v}\right)=\frac{\operatorname{w}_{X}\left(u\right)}{\binom{k+1}{k-1}}$
(1)

Note that:

$\left\\{(u,u^{\prime})\in\hat{R}^{k}(X)(1)\middle|u\cap
u^{\prime}=\check{v}\right\\}=\left\\{r^{k-1,w}_{\check{v}}\middle|w\in\operatorname{\Gamma}^{k+1}(\left\\{u\right\\})\right\\}$

Therefore, for every $\check{v}\in X(k-1)$ it holds that:

$\displaystyle\sum_{\begin{subarray}{c}(u,u^{\prime})\in\hat{R}^{k}(X)(1)^{+}\\\
u\cap
u^{\prime}=\check{v}\end{subarray}}{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,u^{\prime})\right)}$
$\displaystyle=\left\|\left\\{r^{k-1,w}_{\check{v}}\middle|w\in\operatorname{\Gamma}^{k+1}(\left\\{u\right\\})\right\\}\right\|_{\hat{R}^{k}(X)}=\frac{\left\|\operatorname{\Gamma}^{k+1}(\left\\{u\right\\})\right\|_{X}}{\binom{k+2}{k}}=$
$\displaystyle=\frac{\binom{k+2}{k+1}\left\|\left\\{u\right\\}\right\|_{X}}{\binom{k+2}{k}}=\frac{2}{k+1}\left\|\left\\{u\right\\}\right\|_{X}=\frac{2}{k+1}\operatorname{w}_{X}\left(u\right)$

Combining this with 1 completes the proof. ∎

Consider the proof of Lemma A.6. In that proof a special core was selected for
every face (which we termed the canonical core). Using these cores we showed a
connection between the distance of a cocycle and the coboundaries and some
non-trivial condition on its attachment maps. We will now refine that
connection by showing that, with a careful selection of the canonical cores,
one can bound the distance of a cocycle and the coboundaries using the
distance of the attachment maps from the coboundaries. Let us begin by showing
the following:

######  Lemma A.15.

Let $\psi$ be a cochain in $\hat{R}^{k-1}(X)$ then there exists a choice of
$\left\\{c_{u}\right\\}_{u\in\hat{R}^{k}(X)(0)}$ such that:

$\sum_{u\in
X(k)}{\sum_{\begin{subarray}{c}(c_{u},\check{v})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{v})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((c_{u},\check{v})\right)}}\leq\frac{2}{k+1}\left\|\psi\right\|_{\hat{R}^{k-1}(X)}$

###### Proof.

Let $\epsilon_{u}$ be the error seen by edges that represent $u$:

$\epsilon_{u}=\left\|\left\\{(\check{v},\check{w})\in\hat{R}^{k-1}(X)(1)\middle|\check{v}\cup\check{w}=u,\psi(\check{v},\check{w})\neq
1\right\\}\right\|$

We note that:

$2\epsilon_{u}=\sum_{\check{v}\in\binom{u}{k}}{\sum_{\begin{subarray}{c}(\check{v},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(\check{v},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}}$

Note that every face on which $\psi$ differs from $1$ is summed twice (once
for each orientation). Pick, for every face $u\in\hat{R}^{k}(X)$, a core
$c_{u}$ such that:

$\forall\check{v}\in\binom{u}{k}:\sum_{\begin{subarray}{c}(c_{u},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}\leq\sum_{\begin{subarray}{c}(\check{v},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(\check{v},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}$

Using this new definition we can see that:

$\displaystyle 2\epsilon_{u}$
$\displaystyle=\sum_{\check{v}\in\binom{u}{k}}{\sum_{\begin{subarray}{c}(\check{v},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(\check{v},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}}\geq$
$\displaystyle\geq\sum_{\check{v}\in\binom{u}{k}}{\sum_{\begin{subarray}{c}(c_{u},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((c_{u},\check{w})\right)}}=(k+1)\sum_{\begin{subarray}{c}(c_{u},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}$

We finish the proof by noting that:

$\left\|\psi\right\|_{\hat{R}^{k-1}(X)}=\sum_{u\in
X(k)}{\epsilon_{u}}\geq\frac{k+1}{2}\sum_{\begin{subarray}{c}(c_{u},\check{w})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{w})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k+1}(X)}\left((\check{v},\check{w})\right)}$

∎

We are now ready to show a connection between the distance of a cocycle from
the coboundaries and the distance of its attachment maps from the
coboundaries. Specifically we show that:

######  Lemma A.16.

Let ${F}\in Z^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ be a cocycle and
${\widetilde{F}}$ be the coboundary constructed in Lemma A.6. In addition, let
$\check{\varphi}\in B^{1}\left(\hat{R}^{k-1}(X);S_{l}\right)$ and
$\check{\psi}\in C^{1}\left({\hat{R}^{k-1}(X);S_{l}}\right)$ such that
$\check{\varphi}$ is the closest coboundary to ${\check{F}}$ and
$\check{\varphi}={\check{F}}\check{\psi}^{-1}$. The following holds:

$\operatorname{dist}_{\hat{R}^{k}(X)}({F},{\widetilde{F}})\leq
2\frac{k}{k-1}\left\|\check{\psi}\right\|$

###### Proof.

Let $\left\\{c_{u}\right\\}_{u\in\hat{R}^{k}(X)(0)}$ be the canonical cores
chosen as in Lemma A.15. Consider the following:

$\displaystyle\operatorname{dist}_{\hat{R}^{k}(X)}({F},{\widetilde{F}})$
$\displaystyle=\left\|\left\\{(u,u^{\prime})\in\hat{R}^{k}(X)\middle|{F}(u,u^{\prime})\neq{\widetilde{F}}(u,u^{\prime})\right\\}\right\|_{\hat{R}^{k}(X)}\leq$
$\displaystyle\leq\left\|\left\\{(u,u^{\prime})\in\hat{R}^{k}(X)\middle|\check{\psi}(c_{u},u\cap
u^{\prime})\neq 1\text{ or }\check{\psi}(c_{u^{\prime}},u\cap
u^{\prime})\right\\}\right\|_{\hat{R}^{k}(X)}\leq$
$\displaystyle\leq\sum_{u\in\hat{R}^{k}(X)(0)}{\sum_{\begin{subarray}{c}\check{v}\in\binom{u}{k}\\\
\psi(c_{u},\check{v})\neq
1\end{subarray}}{\sum_{\begin{subarray}{c}(u,u^{\prime})\in\hat{R}^{k}(X)(1)^{+}\\\
u\cap
u^{\prime}=\check{v}\end{subarray}}{\operatorname{w}_{\hat{R}^{k}(X)}\left((u,u^{\prime})\right)}}}\leq$
$\displaystyle\leq\sum_{u\in\hat{R}^{k}(X)(0)}{\sum_{\begin{subarray}{c}\check{v}\in\binom{u}{k}\\\
\psi(c_{u},\check{v})\neq
1\end{subarray}}{k\operatorname{w}_{\hat{R}^{k-1}(X)}\left((c_{u},\check{v})\right)}}=$
$\displaystyle=k\sum_{u\in\hat{R}^{k}(X)(0)}{\sum_{\begin{subarray}{c}(c_{u},\check{v})\in\hat{R}^{k-1}(X)(1)^{+}\\\
\psi(c_{u},\check{v})\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((c_{u},\check{v})\right)}}\leq$
$\displaystyle\leq
k\frac{2}{k+1}\left\|\check{\psi}\right\|_{\hat{R}^{k-1}(X)}=2\frac{k}{k+1}\left\|\check{\psi}\right\|_{\hat{R}^{k-1}(X)}$

The first inequality is due to Corollary A.7. The second inequality is due to
the fact that edges $(u,u^{\prime})$ for which $\check{\psi}(c_{u},u\cap
u^{\prime})\neq 1$ and $\check{\psi}(c_{u^{\prime}},u\cap u^{\prime})$ are
summed twice. The third inequality is due to Lemma A.14 and the equality that
follows it is due to the fact that any two cores of a single face $u$ in the
$k$-dimensional representation complex intersect on exactly $k-1$ vertices and
their union is exactly $u$. The last inequality is due to Lemma A.15. ∎

###  A.4 Bounding the Distance of a Cochain from the Coboundaries

We are now finally ready to prove that the empty triangle test is indeed a
property test for the coboundaries of the representation complex. We will do
that by analyzing the following process:

  1. 1.

Use the coboundary expansion around every core in order to bound the distance
of ${F}$ from a cocycle ${Z}$.

  2. 2.

Pick a set of functions $h^{c}$ and and find the distance between
${\check{F}}_{\left\\{h^{c}\right\\}}$ and the coboundaries of
$\hat{R}^{k-1}(X)$.

  3. 3.

Use the aforementioned distance in order to bound the distance of ${Z}$ from
the coboundaries.

We will start by analyzing step 3. In order to do so, we will define the
following:

######  Definition A.17.

Let
$\varepsilon_{\blacktriangle}^{k}\left({F}\right)=\left\|\left\\{(u,v,w)\in\hat{R}^{k}(X)(2)\middle|{F}(u,v){F}(v,w){F}(w,u)\neq
1\right\\}\right\|$ be the norm of the triangles that, if chosen, cause
algorithm 8 to reject.
Also let
$\varepsilon_{\triangle}^{k}\left({F}\right)=\sum_{\begin{subarray}{c}\left\\{u,v,w\right\\}\in\hat{R}^{k}(X)(\triangle)\\\
{F}(u,v){F}(v,w){F}(w,u)\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u,v,w)\right)}$ be
the norm of the empty triangles that are rejected by algorithm 8.

######  Note.

The probability that algorithm 8 rejects satisfies:

$\Pr\left[\text{Algorithm~{}\ref{alg:empty-triangle-test}
rejects}\right]=0.5(\varepsilon_{\blacktriangle}^{k}\left({F}\right)+\varepsilon_{\triangle}^{k}\left({F}\right))$

We will start by considering the norm of the empty triangles of an attachment
map. Specifically we will show that any attachment map satisfies every empty
triangle:

######  Lemma A.18.

Let ${\check{{Z}}}\in C^{1}\left(\hat{R}^{k-1}(X);S_{l}\right)$ be an
attachment map of some cocycle
${Z}\in Z^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ then
$\varepsilon_{\triangle}^{k-1}\left({{\check{{Z}}}}\right)=0$.

###### Proof.

Let
$\left\\{\check{u},\check{v},\check{w}\right\\}\in\hat{R}^{k-1}(X)(\triangle)$
and let $\left\\{h^{c}\right\\}_{c\in X(k-1)}$ be the choice of local
functions such that ${Z}(u,v)=h^{u\cap v}(u)\left(h^{u\cap v}(v)\right)^{-1}$
and
${\check{{Z}}}(\check{u},\check{v})=\left(h^{\check{u}}(\check{u}\cup\check{v})\right)^{-1}h^{\check{v}}(\check{u}\cap\check{v})$.
Consider:

$\displaystyle{\check{{Z}}}$
$\displaystyle(\check{u},\check{v}){\check{{Z}}}(\check{v},\check{w}){\check{{Z}}}(\check{w},\check{u})=$
$\displaystyle=\left(h^{\check{u}}(\check{u}\cup\check{v}))\right)^{-1}h^{\check{v}}(\check{u}\cup\check{v})\left(h^{\check{v}}\left(\check{v}\cup\check{w}\right)\right)^{-1}h^{\check{w}}\left(\check{v}\cup\check{w}\right)\left(h^{\check{w}}\left(\check{w}\cup\check{u}\right)\right)^{-1}h^{\check{u}}\left(\check{w}\cup\check{u}\right)$

Note that because $\left\\{\check{u},\check{v},\check{w}\right\\}$ is an empty
triangle it holds that
$\check{u}\cup\check{v}=\check{v}\cup\check{w}=\check{w}\cup\check{u}$ which
completes the proof. ∎

Before we move on to show stronger connections between
$\varepsilon_{\blacktriangle}^{k}\left({{F}}\right)$,
$\varepsilon_{\triangle}^{k}\left({{F}}\right)$,
$\varepsilon_{\blacktriangle}^{k-1}\left({{\check{F}}}\right)$ and
$\varepsilon_{\triangle}^{k-1}\left({{\check{F}}}\right)$ we would first want
to make the connection between the empty triangles that fail the test in the
$k$-th dimension and the triangles that fail the test in the
$\left(k-1\right)$-th dimension.

######  Lemma A.19.

It holds that:

$\displaystyle\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\vphantom{\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
or}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})\neq{G}(\check{v}\cup\check{w},\check{w}\cup
u)\text{ or}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq{G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}}\middle|\right.$
$\displaystyle\left.\vphantom{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)}\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
or}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})\neq{G}(\check{v}\cup\check{w},\check{w}\cup
u)\text{ or}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq{G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}\subseteq$
$\displaystyle\bigcup_{\begin{subarray}{c}(u,v)\in\hat{R}^{k}(X)(1)\\\
{F}(u,v)\neq{G}(u,v)\end{subarray}}{\bigcup_{\begin{subarray}{c}w\in\hat{R}^{k}(X)(0)\\\
(u,v,w)\in\hat{R}^{k}(X)(\triangle)\end{subarray}}{\left\\{(u\cap v,v\cap
w,w\cap u)\right\\}}}$

###### Proof.

Let
$(\check{u},\check{v},\check{w})\in\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
or}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})\neq{G}(\check{v}\cup\check{w},\check{w}\cup
u)\text{ or}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq{G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}$.
Assume WLOG that
${F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})$
and let $u=\check{u}\cup\check{v}$, $v=\check{v}\cup\check{w}$ and
$w=\check{w}\cup\check{u}$ and note that ${F}(u,v)\neq{G}(u,v)$. All we have
left to prove is that $(u,v,w)\in\hat{R}^{k}(X)(\triangle)$ and that
$(u,v),(v,w),(w,u)\in\hat{R}^{k}(X)(1)$ but $u\cap v=\check{v}$, $v\cap
w=\check{w}$ and $w\cap u=\check{u}$ and therefore:

  * •

$\left\\{v\cap u,u\cap w,w\cap v\right\\}\in\hat{R}^{k-1}(X)(2)$ and
$(u,v,w)\in\hat{R}^{k}(X)(\triangle)$

  * •

It holds that $\left|u\right|=\left|v\right|=\left|w\right|=k$, $\left|u\cap
v\right|=\left|v\cap w\right|=\left|w\cap u\right|=k-1$ and $u\cup v=v\cup
w=w\cup u=\check{u}\cup\check{v}\cup\check{w}\in X(k+1)$ therefore, by
definition, it holds that $(u,v),(v,w),(w,u)\in\hat{R}^{k}(X)(1)$.

∎

We will now show connections between
$\varepsilon_{\blacktriangle}^{k}\left({{F}}\right)$,
$\varepsilon_{\triangle}^{k}\left({{F}}\right)$,
$\varepsilon_{\blacktriangle}^{k-1}\left({{\check{F}}}\right)$, and
$\varepsilon_{\triangle}^{k-1}\left({{\check{F}}}\right)$:

######  Lemma A.20.

Let ${F},{G}\in C^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ be two cochains such
that $\operatorname{dist}\left({F},{G}\right)\leq\epsilon$ then
$\varepsilon_{\triangle}^{k}\left({G}\right)\leq\varepsilon_{\triangle}^{k}\left({F}\right)+3\epsilon$

###### Proof.

Consider $\varepsilon_{\triangle}^{k}\left({G}\right)$ and note that:

$\displaystyle\varepsilon_{\triangle}^{k}\left({G}\right)$
$\displaystyle=\left\|\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|{\scriptstyle{G}(\check{u}\cup\check{v},\check{v}\cup\check{w}){G}(\check{v}\cup\check{w},\check{w}\cup\check{u}){G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq
1}\right\\}\right\|_{\hat{R}^{k-1}(X)}\leq$
$\displaystyle\leq\left\|\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w}){F}(\check{v}\cup\check{w},\check{w}\cup\check{u}){F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq
1\text{ and}\\\
{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})={G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
and}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})={G}(\check{v}\cup\check{w},\check{w}\cup\check{u})\text{
and}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})={G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}\cup\vphantom{\cup\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
or}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})\neq{G}(\check{v}\cup\check{w},\check{w}\cup\check{u})\text{
or}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq{G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}}\right.$
$\displaystyle\quad\left.\vphantom{\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w}){F}(\check{v}\cup\check{w},\check{w}\cup\check{u}){F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq
1\text{ and}\\\
{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})={G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
and}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})={G}(\check{v}\cup\check{w},\check{w}\cup\check{u})\text{
and}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})={G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}\cup}\cup\left\\{(\check{u},\check{v},\check{w})\in\hat{R}^{k-1}(X)(2)\middle|\begin{subarray}{c}{F}(\check{u}\cup\check{v},\check{v}\cup\check{w})\neq{G}(\check{u}\cup\check{v},\check{v}\cup\check{w})\text{
or}\\\
{F}(\check{v}\cup\check{w},\check{w}\cup\check{u})\neq{G}(\check{v}\cup\check{w},\check{w}\cup\check{u})\text{
or}\\\
{F}(\check{w}\cup\check{u},\check{u}\cup\check{v})\neq{G}(\check{w}\cup\check{u},\check{u}\cup\check{v})\end{subarray}\right\\}\right\|\leq$
$\displaystyle\leq\varepsilon_{\triangle}^{k}\left({F}\right)+\sum_{\begin{subarray}{c}(u,v)\in\hat{R}^{k}(X)(1)\\\
{F}(u,v)\neq{G}(u,v)\end{subarray}}{\sum_{\begin{subarray}{c}w\in\hat{R}^{k}(X)\\\
\left\\{u,v,w\right\\}\in\hat{R}^{k}(X)(\triangle)\end{subarray}}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left(u\cap
v,v\cap w,w\cap u\right)}}=$
$\displaystyle=\varepsilon_{\triangle}^{k}\left({F}\right)+3\sum_{\begin{subarray}{c}(u,v)\in\hat{R}^{k}(X)(1)\\\
{F}(u,v)\neq{G}(u,v)\end{subarray}}{\operatorname{w}_{\hat{R}^{k}(X)}\left(u,v\right)}\leq\varepsilon_{\triangle}^{k}\left({F}\right)+3\epsilon$

The second inequality is due to Lemma A.19 and the last inequality is due to
Corollary A.12. ∎

######  Lemma A.21.

Let ${Z}$ be a cocycle of dimension $k$ and let $\check{{Z}}$ be an attachment
map of ${Z}$. Then it holds that:

$\varepsilon_{\triangle}^{k}\left({{Z}}\right)=\varepsilon_{\blacktriangle}^{k-1}\left({\check{{Z}}}\right)$

###### Proof.

The proof follows directly from the definition of the attachment map. Let
$\left\\{h_{c}\right\\}_{c\in X(k-1)}$ be the functions from the definition of
the attachment map:

$\displaystyle\varepsilon_{\blacktriangle}^{k-1}\left({\check{{Z}}}\right)$
$\displaystyle=\left\|\left\\{(u,v,w)\in\hat{R}^{k-1}(X)(2)\middle|\check{{Z}}(w\cap
u,u\cap v)\check{{Z}}(u\cap v,v\cap w)\check{{Z}}(v\cap w,w\cap u)\neq
1\right\\}\right\|=$
$\displaystyle=\left\|\left\\{(u,v,w)\in\hat{R}^{k-1}(X)(2)\middle|{\scriptstyle\left(h^{w\cap
u}(u)\right)^{-1}h^{u\cap v}(u)\left(h^{u\cap v}(v)\right)^{-1}h^{v\cap
w}(v)\left(h^{v\cap w}(w)\right)^{-1}h^{w\cap u}(w)\neq 1}\right\\}\right\|=$
$\displaystyle=\left\|\left\\{(u,v,w)\in\hat{R}^{k-1}(X)(2)\middle|{\scriptstyle
h^{u\cap v}(u)\left(h^{u\cap v}(v)\right)^{-1}h^{v\cap w}(v)\left(h^{v\cap
w}(w)\right)^{-1}h^{w\cap u}(w)\left(h^{w\cap u}(u)\right)^{-1}\neq
1}\right\\}\right\|=$
$\displaystyle=\left\|\left\\{(u,v,w)\in\hat{R}^{k-1}(X)(2)\middle|{Z}(u,v){Z}(v,w){Z}(w,u)\neq
1\right\\}\right\|=$
$\displaystyle=\sum_{\begin{subarray}{c}\left\\{u,v,w\right\\}\in\hat{R}^{k}(X)(\triangle)\\\
{Z}(u,v){Z}(v,w){Z}(w,u)\neq
1\end{subarray}}{\operatorname{w}_{\hat{R}^{k-1}(X)}\left((u,v,w)\right)}=\varepsilon_{\triangle}^{k}\left({F}\right)$

∎

All we have left to do is show how to combine Lemma A.20 and Lemma A.15 in
order to prove that algorithm 8 is indeed a test for the coboundaries in
$\hat{R}^{k}(X)$:

######  Lemma A.22.

For every $k$ there exists a linear function $e_{k}$ such that for every
cochain ${F}$:

$\operatorname{dist}\left({F},B^{1}\left(\hat{R}^{k}(X)\right)\right)\leq
e_{k}\left(\varepsilon_{\blacktriangle}^{k}\left({F}\right),\varepsilon_{\triangle}^{k}\left({F}\right)\right)$

###### Proof.

We will prove this Lemma by induction on the dimension of the representation.
Note that $\hat{R}^{0}(X)=X$. Let ${F}\in
C^{1}\left(\hat{R}^{0}(X);S_{l}\right)=C^{1}\left(X;S_{l}\right)$. Due to the
assumption that $X$ is a $\gamma$-coboundary expander there exists a
coboundary ${\widetilde{F}}$ such that
$\operatorname{dist}\left({F},{\widetilde{F}}\right)\leq\frac{1}{\gamma}\varepsilon_{\blacktriangle}^{0}\left({{F}}\right)$.

Assuming that the claim holds for the representation complex of dimension
$k-1$, let ${F}\in C^{1}\left(\hat{R}^{k}(X);S_{l}\right)$ be a cochain.

We start by showing that ${F}$ is close to a cocycle: Due to Lemma 3.25 the
representation complex is expanding (with the same expansion parameter as the
original complex) and therefore there exists a cocycle ${Z}$ such that
$\operatorname{dist}\left({F},{Z}\right)\leq\frac{1}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right)$.
In addition, due to Lemma A.12 it holds that
$\varepsilon_{\triangle}^{k}\left({{Z}}\right)\leq\varepsilon_{\triangle}^{k}\left({F}\right)+\frac{3}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right)$.

Then we show that this cocycle is close to a coboundary: Consider an
attachment map ${Z}^{\prime}$ of ${Z}$. Due to Lemma A.18 it holds that
$\varepsilon_{\triangle}^{k-1}\left({\check{{Z}}}\right)=0$ and due to Lemma
A.21
$\varepsilon_{\blacktriangle}^{k-1}\left({\check{{Z}}}\right)\leq\varepsilon_{\triangle}^{k}\left({{Z}}\right)\leq\varepsilon_{\triangle}^{k}\left({F}\right)+\frac{3}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right)$.
Due to our assumption it holds that
$\operatorname{dist}\left({Z},B^{1}\left(\hat{R}^{k-1}(X;S_{l})\right)\right)\leq
e(\varepsilon_{\blacktriangle}^{k-1}\left({\check{{Z}}}\right),\varepsilon_{\triangle}^{k-1}\left({\check{{Z}}}\right))$.
We finish this part of the proof by using Lemma A.15 in order to prove that
there exists a coboundary $\widetilde{{Z}}$ such that:

$\operatorname{dist}\left({Z},\widetilde{{Z}}\right)\leq
2\frac{k}{k-1}e(\varepsilon_{\blacktriangle}^{k-1}\left({\check{{Z}}}\right),\varepsilon_{\triangle}^{k-1}\left({\check{{Z}}}\right))=2\frac{k}{k+1}\cdot
e\left(\varepsilon_{\triangle}^{k}\left({F}\right)+\frac{3}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right),0\right)$

All we have left is to use the triangle inequality in order to bound the
distance of ${F}$ from $\widetilde{{Z}}$:

$\operatorname{dist}\left({F},\widetilde{{Z}}\right)\leq\operatorname{dist}\left({F},{Z}\right)+\operatorname{dist}\left({Z},\widetilde{{Z}}\right)\leq\frac{1}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right)+2\frac{k}{k+1}\cdot
e\left(\varepsilon_{\triangle}^{k}\left({F}\right)+\frac{3}{\gamma}\varepsilon_{\blacktriangle}^{k}\left({F}\right),0\right)$

Note that if $e_{k-1}$ is linear then so is $e_{k}$ ∎

We move on to finding $e_{k}$ explicitly

######  Lemma A.23.

For every $k$ it holds that:

$e_{k}\left(\varepsilon_{\blacktriangle},\varepsilon_{\triangle}\right)=\frac{1}{\gamma}\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\varepsilon_{\blacktriangle}+\frac{2}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\epsilon_{\triangle}$

###### Proof.

In order to present $e_{k}$ explicitly we consider the following properties:

  1. 1.

$\forall
k:e_{k}(\varepsilon_{\blacktriangle},\varepsilon_{\triangle})=\frac{\varepsilon_{\blacktriangle}}{\gamma}+2\frac{k}{k+1}\cdot
e_{k-1}\left(\varepsilon_{\triangle}+\frac{3\varepsilon_{\blacktriangle}}{\gamma},0\right)$

  2. 2.

$e_{0}(\varepsilon_{\blacktriangle},\varepsilon_{\triangle})=\frac{\varepsilon_{\blacktriangle}}{\gamma}$

  3. 3.

$\forall
k:e_{k}(\varepsilon_{\blacktriangle},\varepsilon_{\triangle})=\frac{\varepsilon_{\blacktriangle}}{\gamma}+e_{k}\left(0,\varepsilon_{\triangle}+\frac{3\varepsilon_{\blacktriangle}}{\gamma}\right)$

Note that the first two properties were proven in Lemma A.22 and property 3
is, in essence, a restatement of Lemma A.20202020The inequality Lemma A.20
bounds the distance from above and since we are looking for a bound from above
we can consider the case where $e_{k}$ equals its upper bound.. We will begin
with analyzing how $e_{k}$ behaves under the assumption that
$\epsilon_{\triangle}=0$. We will then use property 3 to find $e_{k}$
explicitly.

Let us begin by showing that:

$e_{k}(\varepsilon_{\blacktriangle},0)=\frac{1}{\gamma}\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\varepsilon_{\blacktriangle}$
(2)

We will prove this by induction on $k$. Note that when $k=0$ it is easy to see
that:

$e_{0}(\varepsilon_{\blacktriangle},0)=\frac{\varepsilon_{\blacktriangle}}{\gamma}$

Assume that equation 2 holds for $k-1$ and consider the following:

$\displaystyle e_{k}(\varepsilon_{\blacktriangle},0)$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+2\frac{k}{k+1}\cdot
e_{k-1}\left(\frac{3\varepsilon_{\blacktriangle}}{\gamma},0\right)=\frac{\varepsilon_{\blacktriangle}}{\gamma}+2\frac{k}{k+1}\cdot\frac{1}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\frac{3\varepsilon_{\blacktriangle}}{\gamma}=$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+\frac{6}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\frac{\varepsilon_{\blacktriangle}}{\gamma}=\frac{\varepsilon_{\blacktriangle}}{\gamma}+\left(\sum_{i=1}^{k-1}{\frac{k+2-(i+1)}{k+1}\left(\frac{6}{\gamma}\right)^{i}}\right)\frac{\varepsilon_{\blacktriangle}}{\gamma}=$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+\left(\sum_{i=2}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\frac{\varepsilon_{\blacktriangle}}{\gamma}=\left(\sum_{i=2}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}+1\right)\frac{\varepsilon_{\blacktriangle}}{\gamma}=$
$\displaystyle=\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\frac{\varepsilon_{\blacktriangle}}{\gamma}$

Now all we have left is to use property 1 and property 3 to find $e_{k}$
explicitly:

$\displaystyle e_{k}(\varepsilon_{\blacktriangle},\varepsilon_{\triangle})$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+2\frac{k}{k+1}\cdot
e_{k-1}\left(\varepsilon_{\triangle}+\frac{3\varepsilon_{\blacktriangle}}{\gamma},0\right)=$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+2\frac{k}{k+1}\frac{1}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\left(\varepsilon_{\triangle}+\frac{3\varepsilon_{\blacktriangle}}{\gamma}\right)=$
$\displaystyle=\frac{\varepsilon_{\blacktriangle}}{\gamma}+\frac{2}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\left(\varepsilon_{\triangle}+\frac{3\varepsilon_{\blacktriangle}}{\gamma}\right)=$
$\displaystyle=\frac{1}{\gamma}\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\varepsilon_{\blacktriangle}+\frac{2}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\epsilon_{\triangle}$

∎

We can now finally prove that the empty triangle test is indeed a test for the
property that a cochain ${F}$ is a coboundary:

######  Lemma A.24.

Algorithm 8 is a test for whether a cochain ${F}$ is a coboundary that
performs exactly three queries and, if it rejects ${F}$ with probability of
$\varepsilon(f)$ then:

$\operatorname{dist}\left({F},B^{1}\left(\hat{R}^{k}(X)\right)\right)\leq
2\left(\frac{1}{\gamma}\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)+\frac{2}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\right)\varepsilon({F})$

###### Proof.

Denote the probability that Algorithm 8 rejects ${F}$ as $\varepsilon({F})$
and consider the rejection probability of Algorithm 8 and note that:

$\varepsilon({F})=0.5\varepsilon_{\blacktriangle}^{k}\left({F}\right)+0.5\varepsilon_{\triangle}^{k}\left({F}\right)$

Therefore $\varepsilon_{\blacktriangle}^{k}\left({F}\right)\leq
2\varepsilon({F})$ and $\varepsilon_{\triangle}^{k}\left({F}\right)\leq
2\varepsilon({F})$. Using Lemma A.23 and Lemma A.22 we conclude that:

$\operatorname{dist}\left({F},B^{1}\left(\hat{R}^{k}(X)\right)\right)\leq
2\left(\frac{1}{\gamma}\left(\sum_{i=1}^{k}{\frac{k+2-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)+\frac{2}{\gamma}\left(\sum_{i=1}^{k-1}{\frac{k+1-i}{k+1}\left(\frac{6}{\gamma}\right)^{i-1}}\right)\right)\varepsilon({F})$

∎

Note that Lemma 3.26 and Lemma A.24 are essentially the same.

##  Appendix B Lower Bound on the Number of Queries

In this section we will show that every test that tests list agreement has to
perform at least $l-1$ queries. We will do so by finding a non-agreeing
$l$-assignment ${\mathscr{{R}}}$ such that for any $l-1$ queries there exists
an agreeing $l$-assignment ${\mathscr{{A}}}$ such that the values returned by
the queries are the same when querying ${\mathscr{{A}}}$ and
${\mathscr{{R}}}$. Note that this is enough due to Lemma 7.2.

######  Definition B.1.

Let ${F}_{0},\dots,{F}_{l-1}$ be cochains and let ${\tau}\in X(k)$ be a face.
Also let ${F}_{l}$ be a cochain such that:

$\exists{\tau}^{\prime}\in\binom{{\tau}}{k}\forall
i\in[l]\exists{v}\in{\tau}^{\prime}:{F}_{i}({v})\neq{F}_{l}({v})$

Define the $l$-assignment ${\mathscr{{R}}}$ to be the $l$-assignment that if
$i\neq l$ or ${\sigma}\neq{\tau}$ then
${\mathscr{{R}}}^{\sigma}_{i}={F}_{i}|_{\sigma}$ and
${\mathscr{{R}}}^{\tau}_{l}={F}_{l}|_{\tau}$

All that is left is to show that ${\mathscr{{R}}}$ satisfies the requirements
of Lemma 7.2.

######  Lemma B.2.

${\mathscr{{R}}}$ is not an agreeing $l$-assignment.

###### Proof.

Let $\tilde{{\tau}}\in X(k)$ such that
$\tilde{{\tau}}\cap{\tau}={\tau}^{\prime}$. Note that for every $i$ it holds
that:

${F}_{l}|_{{\tau}\cap\tilde{{\tau}}}\neq{F}_{i}|_{{\tau}\cap\tilde{{\tau}}}$
(3)

If ${\mathscr{{R}}}$ is an agreeing $l$-assignment then there are cochains
${F}^{\prime}_{0},\dots,{F}^{\prime}_{l-1}$ and
$\pi_{\tilde{{\tau}}},\pi_{\tau}$ such that:

$\forall
i:{F}^{\prime}_{i}|_{{\tau}}={\mathscr{{R}}}^{{\tau}}_{\pi_{\tau}(i)}\text{
and
}{F}^{\prime}_{i}|_{\tilde{{\tau}}}={\mathscr{{R}}}^{\tilde{{\tau}}}_{\pi_{\tilde{{\tau}}}(i)}$

Therefore:

${F}_{l}|_{{\tau}\cap\tilde{{\tau}}}={\mathscr{{R}}}^{{\tau}}_{l-1}|_{{\tau}\cap\tilde{{\tau}}}={F^{\prime}}_{\pi_{\tau}^{-1}(l-1)}|_{{\tau}\cap\tilde{{\tau}}}={\mathscr{{R}}}^{\tilde{{\tau}}}_{\pi_{\tilde{{\tau}}(\pi_{\tau}^{-1}(l-1))}}|_{{\tau}\cap\tilde{{\tau}}}={F}_{\pi_{\tilde{{\tau}}}(\pi_{\tau}^{-1}(l-1))}|_{{\tau}\cap\tilde{{\tau}}}$

Which contradicts 3. ∎

######  Lemma B.3.

For every set of queries $q_{1},\dots,q_{l-1}$ to ${\mathscr{{R}}}$ there
exists an agreeing $l$-assignment
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}$ such that when querying
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}$ with
$q_{1},\dots,q_{l-1}$ the results are the same as the results on the original
assignment.

###### Proof.

Note that the queries are of the form $\left({\sigma}_{i},a_{i}\right)$ where
${\sigma}_{i}\in X(k)$ and $a_{i}\in\left[l\right]$. Let
$a^{\prime}\in\left[l\right]$ such that $a^{\prime}\neq a_{i}$ for any $i$. If
$a^{\prime}=l-1$ then
${{\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}}_{i}^{\sigma}={F}_{i}|_{\sigma}$
(which is an agreeing assignment). Otherwise define
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}$ in the following way:

  * •

If $i\neq a^{\prime}$ set
${{\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}}_{i}^{\tau}={\mathscr{{F}}}^{\tau}_{i}$

  * •

Set
${{\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}}_{a^{\prime}}^{\tau}={\mathscr{{F}}}^{\tau}_{l-1}$

  * •

If ${\sigma}\neq{\tau}$ set
${{\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}}_{a^{\prime}}^{\sigma}={{F}_{l}}|_{\sigma}$

And note that ${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}$ agrees with
${F}_{1},\dots,{F}_{a^{\prime}-1},{F}_{a^{\prime}+1},\dots,{F}_{l-1},{F}_{l}$
which completes the proof. Finally note that for every query
$\left({\sigma}_{i},a_{i}\right)$ it holds that
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}[\left({\sigma}_{i},a_{i}\right)]={\mathscr{{R}}}[\left({\sigma}_{i},a_{i}\right)]$
since ${\mathscr{{R}}}$ and
${\mathscr{{A}}}_{\left(q_{1},\dots,q_{l-1}\right)}$ differ only when
$a_{i}=a^{\prime}$ which is never queried. ∎

##  Appendix C Combinatorial Bounds

######  Lemma C.1.

$\binom{d-k+1}{i}\binom{d+1}{k}=\binom{k+i+1}{k}\binom{d+1}{k+i+1}$

###### Proof.

$\displaystyle\binom{d-k+1}{i}\binom{d+1}{k}$
$\displaystyle=\frac{(d-k+1)!}{(i+1)!(d-k-i)!}\frac{(d+1)!}{k!(d-k+1)!}$
$\displaystyle=\frac{(k+i+1)!}{(i+1)!(d-k-i)!}\frac{(d+1)!}{k!(k+i+1)!}$
$\displaystyle=\frac{(k+i+1)!}{(i+1)!k!}\frac{(d+1)!}{(k+i+1)!(d-k-i)!}$
$\displaystyle=\binom{k+i+1}{k}\binom{d+1}{k+i+1}$

∎