Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses a random pair of $k$-element subsets that intersect on $\sqrt k$ elements, and accepts if the local functions agree on the common elements.

The small soundness (or $1\%$) regime is concerned with the structure of ensembles $\{f_s\}$ that pass the test with small but non-negligible probability $Agree (\{f_s\}) \geq \epsilon>0$. A "classical" small-soundness agreement theorem is a list-decoding statement, saying that
$Agree(\{f_s\}) > \epsilon$ ==> there are $G^1,..., G^\ell$, s.t. $\Pr_s[f_s= G^i|_s]\geq poly(\epsilon)$, i=1,...,$\ell$.

Such a statement is motivated by PCP questions and has been shown in the case where X is the complete k-dimensional complex or where X is a collection of low dimensional subspaces of a vector space.
In this work we study small soundness behavior of agreement tests on high dimensional expanders X. Such complexes are known to satisfy agreement tests in the high soundness (99%) regime, and it has been an open challenge to analyze their small soundness behavior.

Surprisingly, the small soundness behavior turns out to be governed by the topological covers of X. We show that:

1. If X has no connected covers, then a "classical" small soundness theorem as in above holds, provided that X satisfies an additional expansion property.

2. If X has a connected cover, then "classical" small soundness as above necessarily fails.

3. If X has a connected cover (and assuming the additional expansion property),
we replace the failed soundness by a slightly weaker statement, which we call lift-decoding:
$Agree(\{f_s\})> \epsilon$ ==> there is a cover $\rho:Y\to X$, and $G:Y(0)\to\Sigma$, such that $\Pr_{\tilde s\to s}[f_s = G|_{\tilde s}] \geq poly(\epsilon)$,
where $\tilde s\to s$ means that $\rho(\tilde s)=s$.

The additional expansion property is cosystolic expansion of a complex derived from X. This property holds for the spherical building and for quotients of the Bruhat-Tits building, giving us new examples for set systems with small soundness agreement theorems.

Given a family X of subsets of [n] and an ensemble of local functions $\{f_s:s\to\Sigma \;|\; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. For example, the V-test chooses a random pair of $k$-element subsets that intersect on $\sqrt k$ elements, and accepts if the local functions agree on the common elements.

The small soundness (or $1\%$) regime is concerned with the structure of ensembles $\{f_s\}$ that pass the test with small but non-negligible probability $Agree (\{f_s\}) \geq \epsilon>0$. A "classical" small-soundness agreement theorem is a list-decoding statement, saying that
$Agree(\{f_s\}) > \epsilon$ ==> there are $G^1,..., G^\ell$, s.t. $\Pr_s[f_s= G^i|_s]\geq poly(\epsilon)$, i=1,...,$\ell$.

Such a statement is motivated by PCP questions and has been shown in the case where X is the complete k-dimensional complex or where X is a collection of low dimensional subspaces of a vector space.
In this work we study small soundness behavior of agreement tests on high dimensional expanders X. Such complexes are known to satisfy agreement tests in the high soundness (99%) regime, and it has been an open challenge to analyze their small soundness behavior.

Surprisingly, the small soundness behavior turns out to be governed by the topological covers of X. We show that:

1. If X has no connected covers, then a "classical" small soundness theorem as in above holds, provided that X satisfies an additional expansion property.

2. If X has a connected cover, then "classical" small soundness as above necessarily fails.

3. If X has a connected cover (and assuming the additional expansion property),
we replace the failed soundness by a slightly weaker statement, which we call lift-decoding:
$Agree(\{f_s\})> \epsilon$ ==> there is a cover $\rho:Y\to X$, and $G:Y(0)\to\Sigma$, such that $\Pr_{\tilde s\to s}[f_s = G|_{\tilde s}] \geq poly(\epsilon)$,
where $\tilde s\to s$ means that $\rho(\tilde s)=s$.

The additional expansion property is cosystolic expansion of a complex derived from X. This property holds for the spherical building and for quotients of the Bruhat-Tits building, giving us new examples for set systems with small soundness agreement theorems.