Observe that $\operatorname*{\mathbb{E}}[g]\geqslant\delta^{\prime}$ since by
assumption $s\notin L$. Moreover by construction we have $v\in D^{\prime}$ if
and only if $\operatorname*{\mathbb{E}}_{{t_{0}\ni
v}}\left[g(t_{0})\right]\leqslant\frac{1}{3}\operatorname*{\mathbb{E}}[g(t_{0})]$.

The problem is now reduced to sampling on the complete complex. In other words
let $L=\binom{s}{|t^{\prime}|}$, $R=s$ and $v\sim t$ if $v\in t$. By Chernoff
for every $\alpha$, this graph is an
$(\alpha,\beta,\frac{1}{2})$-multiplicative sampler for
$\beta=\exp(-\Omega(\alpha k))$. By Claim 4.8, this implies that the opposite
graph is a $(\frac{6\beta}{\alpha},2\alpha,\frac{2}{3})$-multiplicative
sampler. We take $\alpha=\eta^{\prime}/2$, and the constant $c_{5}>0$ defined
above small enough so that $\frac{6\beta}{\alpha}\leqslant\delta^{\prime}$. As
such we have for every function $g:L\to[0,1]$ of expectation at least
$\delta^{\prime}$ the fraction of vertices $v\in s$ such that
$\operatorname*{\mathbb{E}}_{{t^{\prime}\subseteq s,v\in
t^{\prime}}}\left[g\right]<\frac{1}{3}\operatorname*{\mathbb{E}}_{{t^{\prime}\subseteq
s}}\left[g(t^{\prime})\right]$ is at most $\eta^{\prime}$ as desired. ∎

###  8.4 Examples of Global Complexes

We conclude the section with several examples of ‘global HDX’ to which Theorem
8.7 applies in a blackbox manner. We start with a few basic direct examples
and then argue a vast array of complexes studied in the approximate sampling
literature give rise to global HDX. These are:

  1. 1.

The complete complex.

  2. 2.

Erdos-Renyi Hypergraphs.

  3. 3.

Skeletons of the full linear matroid over $\mathbb{F}_{q}^{d}$.

  4. 4.

Skeletons of $\ell_{\infty}$-independent complexes, including many classic
spin systems.

  5. 5.

Faces complexes of any of the above.

The first and simplest example of global complexes (other than the complete
complex) come from the classical random model of Linial and Meshulam [LM06].

######  Definition 8.20 (Erdos-Renyi Hypergraphs).

The Erdos-Renyi hypergraph $X\sim G_{k}(n,p)$ is a random $k$-uniform
simplicial complex whose $(k-1)$-skeleton is complete, and such that every
$k$-face is sampled into $X$ with probability $p$ independently.

The second direct example we’ll give is based on the full linear matroid over
$\mathbb{F}_{q}^{d}$, whose faces consist of linearly independent vectors over
$\mathbb{F}_{q}^{d}$:

$\X[i]=\left\\{\\{v_{1},v_{2},\dots,v_{i}\\}\left|\;\vphantom{\\{v_{1},v_{2},\dots,v_{i}\\}{v_{1},v_{2},\dots,v_{i}}\text{
are independent}}\right.{v_{1},v_{2},\dots,v_{i}}\text{ are
independent}\right\\},$

endowed with the uniform distribution.

######  Claim 8.21 (Global complexes).

The following families are global and HDX:

  1. 1.

The $k$-uniform complete complex on $n$ vertices for large enough $n$ is:

     * –

(one-sided) $0$-local-spectral HDX

     * –

$n^{-\Omega(k)}$-global

  2. 2.

The Erdos-Renyi hypergraph $G_{k}(n,p)$ for large enough $n$ is w.h.p:

     * –

$o_{n}(1)$-local-spectral HDX

     * –

$(1-p+o_{n}(1))$-global

  3. 3.

The $k$-skeleton of the full linear matroid over $\mathbb{F}_{q}^{d}$ for
large enough $q,d$ is :

     * –

(one-sided) $0$-local-spectral HDX

     * –

$q^{-\Omega(d)}$-global

###### Proof.

We cover each case individually:

##### Complete Complex

All links of the complete complex are complete and therefore $0$-one-sided
local spectral expanders. For globalness, observe that the only
$\frac{k}{2}$-sets which do not appear in the link of some $t$ are those that
intersect it, which are an $1-\frac{\binom{n-k}{k}}{\binom{n}{k}}\leqslant
n^{-\Omega(k)}$ fraction.

##### Random Hypergraphs

It is well known for fixed $p$ that this complex is an $o_{n}(1)$-local-
spectral expander with high probability so long as $p\gg\frac{k\log(n)}{n}$
(the top links are simply random $G(n,p)$ graphs). Since all other links are
at least connected with high probability, Theorem 4.23 implies the local-
spectral bound. Toward globality, fix any $\frac{k}{2}$-set
$t\subset\binom{[n]}{k/2}$. By Chernoff the probability that more than
$(1-p+o_{n}(1))$-fraction of $\frac{k}{2}$-sets disjoint from $t$ fail to
appear in $X$ is much less than $n^{-\Omega(k)}$ for large enough $n$. Thus
union bounding over $t$, the worst-case total variation of $S_{t}$ from
uniform over ${\binom{n}{\frac{k}{2}}}$ is at most $1-p+o_{n}(1)$ as
desired.121212Formally, distance here should be measured from
$\pi_{\frac{k}{2}}$, but this is within $o_{n}(1)$ of uniform in TV with high
probability.

##### Linear Matroid

All matroids (and therefore their skeletons) are $0$-local spectral expanders
[Ana+19] (for this matroid specifically, it is folklore). Toward globality,
fix $\frac{k}{2}$ linearly independent vectors
$B_{1}=\\{v_{1},\ldots,v_{k/2}\\}$. The set $B_{2}=\\{w_{1},\ldots,w_{k/2}\\}$
only fails to appear in the link of $B_{1}$ if $B_{1}$ and $B_{2}$ are
linearly dependent, which happens with probability roughly
$\frac{q^{k+(k-1)d}}{q^{dk}}\leqslant q^{-\Omega(d)}$ (ignoring low-order
terms). Since $\Pi_{k/2}$ is uniform over linearly independent sets this gives
the result. ∎ The sampling literature is rife with examples of
“$\ell_{\infty}$-independent” complexes (a term formally coined in [KKS21]),
which are closely related to global complexes. We’ll consider the variant
implicit in [CLV21]. Let $\mu$ be a distribution over $[q]^{d}$, and observe
$\mu$ induces a natural $d$-partite simplicial complex $X_{\mu}$ with

$\X[d][\mu]\coloneqq\\{(1,a_{1}),\ldots,(d,a_{d}):(a_{1},\ldots,a_{d})\in
Supp(\mu)\\}$

and $\pi_{X}((1,a_{1}),\ldots,(d,a_{d}))=\mu(a_{1},\ldots,a_{d})$. Let
$S\subset[d]$ and $z\in[q]^{S}$ be such that
$\operatorname*{\mathbb{P}}_{x\sim\mu}[x_{S}=z]>0$ (we call such
configurations ‘feasible’). The $(S,z)$-influence matrix $\Psi_{z\to S}$ has
entries

$\Psi_{z\to
S}((u,i),(v,j))=\begin{cases}\operatorname*{\mathbb{P}}_{x\sim\mu}[x_{i}=u|x_{j}=v,x_{S}=z]-\operatorname*{\mathbb{P}}_{x\sim\mu}[x_{i}=u|x_{S}=z]&\text{if
$j\neq i$}\\\ 0&\text{if $j=i$}.\end{cases}$

A complex is called $\ell_{\infty}$-independent if $\lVert\Psi\rVert_{\infty}$
is bounded for all feasible configurations.

######  Definition 8.22 ($\ell_{\infty}$-independence).

Fix $q,d\in\mathbb{N}$ and let $\mu$ be a distribution over $[q]^{d}$. $\mu$
is called $D$-$\ell_{\infty}$-independent if for all feasible $S\subset[d]$
and $z\in\\{0,1\\}^{S}$:

$\lVert\Psi_{S\to z}\rVert_{\infty}\leqslant D.$

We remark that in this regime, one typically thinks of $q$ as fixed or small
and the uniformity $d$ as going to infinity. We show any sufficiently low-
dimensional skeleton of an $\ell_{\infty}$-independent complex is a global
HDX:

######  Proposition 8.23.

Let $\mu$ be a $D$-$\ell_{\infty}$-independent distribution over $[q]^{d}$ and
$3\leqslant k\leqslant d$. Then the $k$-skeleton $X_{\mu}^{\leqslant k}$
satisfies:

  1. 1.

$X_{\mu}^{\leqslant k}$ is a $\frac{D+q}{d+3-k}$-two-sided local-spectral
expander

  2. 2.

$X_{\mu}^{\leqslant k}$ is $\frac{k^{2}}{8}\cdot\frac{D+q}{d+3-k}$-global.

We remark that (tighter) spectral variants of both items above are well known
(see e.g. [ALG21, AP23]). Proposition 8.23 implies essentially every spin-
system studied in the recent breakthrough line of work on approximate sampling
through spectral independence admits optimal 1% agreement testers (taking
$k\leqslant\sqrt{\log(d)}$ skeletons).131313Note while spectral independence
is weaker than what we require, almost all known methods for spin systems
actually bound $\ell_{\infty}$-independence. See [KKS21, Section 3] for an
overview including distributions with the stochastic covering property,
independent sets, various Ising/Potts models, list colorings, and more.

The proof of Proposition 8.23 relies on an intermediate notion of [Hop24]
called local-$\ell_{\infty}$-expansion.

######  Definition 8.24 ($(\lambda,\infty)$-expansion).

A simplicial complex $X$ is called a $(\lambda,\infty)$-local expander if for
every $\tau\in X$ with $|\tau|\leqslant d-2$:

$\lVert A_{\tau}-\Pi_{\tau}\rVert_{\infty}\leqslant\lambda$

where $A_{\tau}$ is the weighted adjacency matrix of $X_{\tau}$’s 1-skeleton,
and $\Pi_{\tau}$ is its corresponding stationary operator.

We require two lemmas regarding this notion. First, we note that up to
dependence on the alphabet $q$ (typically thought of as constant in this
regime) $\ell_{\infty}$-expansion is essentially equivalent to
$\ell_{\infty}$-independence.

######  Lemma 8.25.

Let $\mu$ be a $D$-$\ell_{\infty}$-independent distribution over $[q]^{d}$.
Then for every feasible $S\subset[d]$ and $x_{S}\in\\{0,1\\}^{S}$:

$\lVert A_{x_{S}}-\Pi_{x_{S}}\rVert_{\infty}\leqslant\frac{D+q}{d-|S|}.$

###### Proof.

We prove the case where $S=\emptyset$. The general statement follows from
applying this argument to the links of $X_{\mu}$. With this in mind, observe
that by definition:

$\displaystyle\lVert A_{\emptyset}-\Pi\rVert_{\infty}=$
$\displaystyle\max_{(u,i)}\sum\limits_{(v,j)\in
X_{(u,i)}}\left|\frac{1}{d-1}\operatorname*{\mathbb{P}}[x_{i}=u|x_{v}=j]-\frac{1}{d}\operatorname*{\mathbb{P}}[x_{i}=u]\right|$
$\displaystyle\leqslant\frac{1}{d}\max_{(u,i)}\left(\sum\limits_{(v,j)\in
X_{(u,i)}}\left|\operatorname*{\mathbb{P}}[x_{i}=u|x_{j}=v]-\operatorname*{\mathbb{P}}[x_{i}=u]\right|+\frac{1}{d-1}\operatorname*{\mathbb{P}}[x_{i}=u|x_{j}=v]\right)$
$\displaystyle\leqslant\frac{q}{d}+\frac{1}{d}\max_{(u,i)}\sum\limits_{(v,j)\in
X_{(u,i)}}\left|\operatorname*{\mathbb{P}}[x_{i}=u|x_{j}=v]-\operatorname*{\mathbb{P}}[x_{i}=u]\right|$
$\displaystyle=\frac{q}{d}+\frac{1}{d}\max_{(u,i)}\sum\limits_{(v,j)\in
X_{(u,i)}}\left|\operatorname*{\mathbb{P}}[x_{i}=u|x_{j}=v]-\operatorname*{\mathbb{P}}[x_{i}=u]\right|$
$\displaystyle\leqslant\frac{D+q}{d}$

∎

Second, we’ll need the slightly more involved fact from [Hop24] that any
$\ell_{\infty}$-local expander is global. We reproduce the proof here for
completeness.

######  Lemma 8.26.

Let $X$ be a $d$-uniform $\lambda$-$\ell_{\infty}$-local expander. Then $X$ is
$\frac{d^{2}}{8}\lambda$-global.

###### Proof.

Recall that it is sufficient to bound the infinity norm:

$\lVert
S_{\frac{d}{2},\frac{d}{2}}-\Pi_{\frac{d}{2},\frac{d}{2}}\rVert_{\infty}\leqslant\frac{d^{2}}{4}\lambda.$

We prove a slightly stronger statement by induction. For any $\tau\in X$ and
feasible $i,j$ both the $\infty$-norm and $1$-norm are bounded by:

$\lVert S^{\tau}_{i,j}-\Pi^{\tau}_{i,j}\rVert_{1},\lVert
S_{i,j}-\Pi_{i,j}\rVert_{\infty}\leqslant ij\lambda.$

We induct on $i+j$. For the base case $i=j=1$, first observe the $\infty$-norm
is exactly the $\lambda$-$\ell_{\infty}$-expansion of the $1$-skeleton. A
classical consequence of Hölder duality states that for any Hölder conjugates
$(p,q)$ and operator $M$

$\lVert M\rVert_{p}=\lVert M^{*}\rVert_{q},$

where $M^{*}$ is $M$’s adjoint. Since $S_{1,1}-\Pi_{1,1}$ is self-adjoint we
therefore have

$\lVert S^{\tau}_{0,0}-\Pi^{\tau}_{0,0}\rVert_{1}=\lVert
S^{\tau}_{0,0}-\Pi^{\tau}_{0,0}\rVert_{\infty}\leqslant\lambda$

as desired.

Assume now by induction that, for some fixed $i+j>0$, all
$i^{\prime}+j^{\prime}<i+j$ and $\tau\in X$ satisfy

$\lVert
S^{\tau}_{i^{\prime},j^{\prime}}-\Pi^{\tau}_{i^{\prime},j^{\prime}}\rVert_{\infty}\leqslant
i^{\prime}j^{\prime}\lambda.$

Let $p\in\\{1,\infty\\}$ and let $\bar{p}$ denote the complement of $p$. We
first argue we may assume without loss of generality that $i>1$. This is again
by Hölder duality since

$\lVert S_{i,j}-\Pi_{i,j}\rVert_{p}=\lVert S_{j,i}-\Pi_{j,i}\rVert_{\bar{p}}.$

Thus we are done if we show the result for both $p\in\\{1,\infty\\}$ just for
the case $i\geqslant j$ (and thus $i>1$).

Toward this end, fix any $f:\X[j]\to\mathbb{R}$. As is typically the case, the
idea is to localize the input by first drawing an $(i-1)$-face, then a vertex
from its link:

$\displaystyle\lVert
S_{i,j}f-\Pi_{i,j}f\rVert_{p}=\Bigg{|}\Bigg{|}\lVert(S_{i,j}f)|_{s}-(\Pi_{i,j}f)|_{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}$

where for any $g\in\X[i]\to\mathbb{R}$, $g|_{s}(v)=g(s\cup v)$ denotes the
localization of $g$ to the link of $s$. For concreteness, we write out the
above explicitly for the $p=1$ case in slightly less compact notation. The
$p=\infty$ case is the same replacing expectations with absolute maxima:

$\displaystyle\lVert S_{i,j}f-\Pi_{i,j}f\rVert_{p}$
$\displaystyle=\underset{t\in\X[i]}{\mathbb{E}}[|S_{i,j}f(t)-\Pi_{i,j}f(t)|]$
$\displaystyle=\underset{{s\in\X[i-1]}}{\mathbb{E}}\Bigg{[}\underset{{v\in\SC[X][1][s]}}{\mathbb{E}}[|S_{i,j}f(s\cup
v)-\Pi_{i,j}f(s\cup v)|]\Bigg{]}$
$\displaystyle=\underset{s\in\X[i-1]}{\mathbb{E}}\Bigg{[}\underset{v\in\SC[X][1][s]}{\mathbb{E}}[|S_{i,j}f|_{s}(v)-\Pi_{i,j}f|_{s}(v)|]\Bigg{]}$
$\displaystyle=\mathbb{E}_{s\in\X[i-1]}\Bigg{[}\mathbb{E}_{v\in\SC[X][1][s]}[|S_{i,j}f|_{s}(v)-\Pi_{i,j}f|_{s}(v)|]\Bigg{]}$
$\displaystyle=\mathbb{E}_{s\in\X[i-1]}\Bigg{[}\Bigg{|}\mathbb{E}_{v\in\SC[X][1][s]}[|S_{i,j}f|_{s}(v)-\Pi_{i,j}f|_{s}(v)|]\Bigg{|}\Bigg{]}$
$\displaystyle=\Bigg{|}\Bigg{|}\lVert(S_{i,j}f)|_{s}-(\Pi_{i,j}f)|_{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}.$

We stick to the more compact norm notation for the remainder of the proof. The
trick is now to observe that as a function of $\SC[X][1][s]$, $S_{i,j}f|_{s}$
is exactly $S_{1,j}^{s}f^{s}$, where $f^{s}:\SC[X][j][s]\to\mathbb{R}$ is the
restriction $f^{s}(\tau)=f(\tau)$. Then by adding and subtracting the
corresponding local stationary operator we have:

$\displaystyle\lVert S_{i,j}f-\Pi_{i,j}f\rVert_{p}$
$\displaystyle=\Bigg{|}\Bigg{|}\lVert
S^{s}_{1,j}f^{s}-\Pi^{s}_{1,j}f^{s}+\Pi^{s}_{1,j}f^{s}-(\Pi_{i,j}f)|_{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}$
$\displaystyle\leqslant\Bigg{|}\Bigg{|}\lVert
S^{s}_{1,j}f^{s}-\Pi^{s}_{1,j}f^{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}+\Bigg{|}\Bigg{|}\lVert\Pi^{s}_{1,j}f^{s}-(\Pi_{i,j}f)|_{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}$

by the triangle inequality. The first term is now bounded by the inductive
hypothesis applied in the link of $s$:

$\Bigg{|}\Bigg{|}\lVert
S^{s}_{1,j}f^{s}-\Pi^{s}_{1,j}f^{s}\rVert_{p,v\in\SC[X][1][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}\leqslant\Bigg{|}\Bigg{|}j\lambda\lVert
f^{s}\rVert_{p,\SC[X][j][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}=j\lVert
f\rVert_{p,\X[j]}$

Toward analyzing the second term, observe that
$\Pi^{s}_{1,j}f^{s}=S_{i-1,j}f(s)$ and $(\Pi_{i,j}f)|_{s}(v)=\Pi_{i-1,j}f(s)$
so:

$\Bigg{|}\Bigg{|}\lVert\Pi^{s}_{1,j}f^{s}-(\Pi_{i,j}f)|_{s}\rVert_{p,v\in\SC[X][0][s]}\Bigg{|}\Bigg{|}_{p,s\in\X[i-1]}=\lVert
S_{i-1,j}f-\Pi_{i-1,j}f\rVert_{p,s\in\X[i-1]}\leqslant(i-1)j\lambda\lVert
f\rVert_{p,\X[j]}$

by the inductive hypothesis. Altogether this gives

$\lVert S_{i,j}f-\Pi_{i,j}f\rVert_{p}\leqslant\lambda
j+\lambda(i-1)j=ij\lambda$

as desired. ∎

The proof of Proposition 8.23 is now essentially immediate.

###### Proof of Proposition 8.23.

The first fact is immediate from Lemma 8.25 and the fact that $\lVert
A_{\tau}-\Pi_{\tau}\rVert_{2}\leqslant\lVert
A_{\tau}-\Pi_{\tau}\rVert_{\infty}$. The second fact is an immediate
consequence of combining Lemma 8.25 and Lemma 8.26. ∎

We conclude the subsection by the observation that if a complex $X$ is global,
then so is its faces complex (Definition 5.7). Since the faces complex also
inherits the two-sided expansion of the original complex up to factors in
uniformity (c.f. the proof of Theorem 5.1), this shows that one can also take
as examples faces complexes of any of the examples above.

######  Claim 8.27.

Let $X$ be a $k$-uniform and $\lambda$-global complex. Let $\ell$ be such that
$\ell$ divides $k$, then the $\ell$-faces complex $F^{\ell}_{X}$ is
$\lambda$-global.

###### Proof.

Let $m=\frac{k}{\ell}$ for notational convenience. Fix
$t=\\{s_{1},s_{2},\dots,s_{\frac{m}{2}}\\}\in F^{\ell}_{X}(\frac{m}{2})$.
Observe that the set of neighbors of $t$ with respect to the swap walk in
$F^{\ell}X$ are exactly those $t^{\prime}$ such that $\cup t$ and $\cup
t^{\prime}$ are neighbors in the swap walk on $\X[\frac{k}{2}]$ (here $\cup
t=s_{1}\cup s_{2}\cup\dots\cup s_{\frac{m}{2}}$ and similarly for
$t^{\prime}$). Moreover, one samples a neighbor of $t$ by sampling a random
neighbor $\tau$ of $\cup t$, and then sampling a uniform at random partition
of $\tau$ to
$t^{\prime}=\\{s_{1}^{\prime},s_{2}^{\prime},\dots,s_{\frac{m}{2}}\\}$ (the
partition is chosen independent of $t$).

Thus one observes that the $TV$-distance between $S_{t}$ and $\Pi$ can be
written as

$\displaystyle\frac{1}{2}\sum_{t^{\prime}\in
F^{\ell}\X[\frac{m}{2}]}|\operatorname*{\mathbb{P}}_{{S_{t}(F^{\ell}X)}}\left[t^{\prime}\right]-\operatorname*{\mathbb{P}}_{{\Pi}}\left[t^{\prime}\right]|$
$\displaystyle=\frac{1}{2}\sum_{\tau\in\X[\frac{k}{2}]}\sum_{t^{\prime}:\cup
t^{\prime}=\tau}|\operatorname*{\mathbb{P}}_{{S_{t}(F^{\ell}X)}}\left[t^{\prime}\right]-\operatorname*{\mathbb{P}}_{{\Pi}}\left[t^{\prime}\right]|$
$\displaystyle=\frac{1}{2}\sum_{\tau\in\X[\frac{k}{2}]}\sum_{t^{\prime}:\cup
t^{\prime}=\tau}p|\operatorname*{\mathbb{P}}_{{S_{\cup
t}(X)}}\left[\tau\right]-\operatorname*{\mathbb{P}}_{{\Pi(X)}}\left[\tau\right]|$

where $p$ is one over the number of partitions of $\tau$ to $t^{\prime}$.
Obviously this is equal to

$\frac{1}{2}\sum_{\tau\in\X[\frac{k}{2}]}\operatorname*{\mathbb{P}}_{{S_{\cup
t}(X)}}\left[\tau\right]-\operatorname*{\mathbb{P}}_{{\Pi(X)}}\left[\tau\right]=d_{TV}(S_{\cup
t}(X),\Pi(X))\leqslant\lambda$

as desired. ∎

##  9 Analytic, Geometric, and Combinatorial Applications

In this section, we cover several brief applications of sampling and reverse
hypercontractivity in well-studied combinatorial and analytic settings.

###  9.1 New Double Samplers

Double samplers are a strengthened notion of sampling introduced in [DK17,
Din+18] that consist of two “stacked” samplers with additional local sampling
properties under ‘closure’ of the top layer. These interesting objects have
powerful applications in agreement testing [DK17] and list-decoding [Din+18],
and have even seen algorithmic use in the construction of space-efficient data
structures for the heavy hitter problem [DW22].

######  Definition 9.1 (Double sampler, [Din+18]).

A double sampler consists of a triple $(V_{2},V_{1},V_{0})$, where $V_{0}$ is
the ground set, $V_{1}$ is a collection of $i$-subsets of $V_{0}$ and $V_{2}$
is a collection of $k$-subsets of $V_{0}$, where $k>i\in\mathbb{N}$. We say
that $(V_{2},V_{1},V_{0})$ is an
$(\varepsilon,\beta,\varepsilon_{0},\beta_{0})$-_double sampler_ if

  * –

The inclusion graphs on $(V_{2},V_{1})$ and $(V_{2},V_{0})$ are
$(\varepsilon,\beta)$-additive samplers and the inclusion graph on
$(V_{1},V_{0})$ is an $(\varepsilon+\varepsilon_{0},\beta+\beta_{0})$-additive
sampler141414The weights over edges in $(V_{i},V_{j})$ are the marginals of
the probabilistic experiment where we first choose $T\in V_{2}$ (according to
some given weight distribution $\Pi$), and then choose $v\in V_{0}$ and $S\in
V_{1}$ such that $v\in S\subseteq T$, uniformly at random over all such pairs
$S,v$. (recall the inclusion graph is defined by connecting two subsets by an
edge if one contains the other).

  * –

For every $T\in V_{2}$, let $V_{1}(T)=\\{S\in V_{1}\;:\;S\subset T\\}$ be the
sets in $V_{1}$ that are contained in $T$. Let $G_{|T}$ be the bipartite
inclusion graph connecting elements in $T$ (viewed as elements in the ground
set $V_{0}$) to subsets in $V_{1}(T)$. We require that for every $T\in V_{2}$,
the graph $G_{|T}$ is an $(\beta_{0},\varepsilon_{0})$-additive sampler.

Double samplers are only known to arise from high dimensional expanders. In
their original work, [DK17, Din+18] use the Ramanujan complexes [LSV05] to
construct explicit double samplers for all
$(\varepsilon,\beta,\varepsilon_{0},\beta_{0})$:

######  Theorem 9.2 ([Din+18, Theorem 2.11]).

For every $(\varepsilon,\beta,\varepsilon_{0},\beta_{0})>0$, there exists an
explicit infinite family of double samplers
$\\{(V_{0}^{(n)},V_{1}^{(n)},V_{2}^{(n)})\\}$ such that for all $n$:

$\frac{|V_{1}^{(n)}|}{|V_{0}^{(n)}|},\frac{|V_{2}^{(n)}|}{|V_{0}^{(n)}|}=\exp\left(\operatorname{poly}\left(\frac{1}{\beta},\frac{1}{\beta_{0}},\frac{1}{\varepsilon},\frac{1}{\varepsilon_{0}}\right)\right).$

One of the main open questions posed in [Din+18] is to settle the overhead of
double samplers. In particular, while it is known that exponential dependence
on $\varepsilon_{i}$ is necessary (even for standard samplers), it is
plausible the dependence on the ‘failure probability’ $\beta_{i}$ could be
improved, perhaps even to match the corresponding polynomial dependence of
optimal standard samplers. Since typical related applications (e.g. for low
soundness agreement tests and PCPs [IKW12, DL17]) take $\varepsilon$ to be
constant (or at most some polylog in $\beta$), this latter dependence is where
the crux of the problem lies.

To the best of our knowledge, there have been no lower bounds or improvements
over Theorem 9.2 since [Din+18]’s original work. Leveraging our concentration
bounds and their corresponding optimality (see Section 11.1) we take a
significant step toward resolving this problem: quasi-polynomial size double
samplers exist and, under reasonable assumptions on the underlying complex,
are the best possible.

######  Theorem 9.3 (Quasi-Polynomial Double Samplers).

for every $(\varepsilon,\beta,\varepsilon_{0},\beta_{0})>0$, there exists an
explicit family of ($\beta,\varepsilon$),$(\beta_{0},\varepsilon_{0})$ double
samplers $\\{(V^{(n)}_{2},V^{(n)}_{1},V^{(n)}_{0})\\}$ of size at most:

$\frac{|V^{(n)}_{1}|}{|V^{(n)}_{0}|},\frac{|V^{(n)}_{2}|}{|V^{(n)}_{0}|}\leqslant\exp\left(\tilde{O}\left(\frac{\log^{3}\frac{1}{\beta}\log^{3}\frac{1}{\beta_{0}}}{\varepsilon^{6}\varepsilon_{0}^{6}}\right)\right).$

Moreover, for $\varepsilon\in(0,0.01)$, if the underlying complex family
$\\{X_{n}\\}$ is $\frac{\varepsilon}{3}$-hitting, vertex-uniform, and non-
contracting,151515Here we mean 1) $\pi_{0}(v)=|\X[1]|^{-1}$ for all
$v\in\X[1]$, and 2) $|\X[i]|\geqslant|\X[i-1]|$ for all $2\leqslant i\leqslant
d$. this is optimal up to polynomial factors in the exponent:

$\frac{|V_{2}^{(n)}|}{|V_{0}^{(n)}|}\geqslant\exp\left(\Omega\left(\frac{\log(\frac{1}{\beta})\log(\frac{1}{\beta_{0}})}{\varepsilon^{2}\varepsilon_{0}^{2}}\right)\right)$

Note the above does not fully rule out the existence of simplicial poly-size
double samplers. While the assumption on regularity in the lower bound can be
easily relaxed, it is unclear to what extent the assumption on hitting-set is
an artifact of our proof technique (see Section 11.1 for details), though it
is certainly a natural property for such objects to satisfy. Moreover, our
bound strongly relies on the assumption that $|V_{2}|\geqslant\exp(d)|V_{0}|$
(implied by $X$ being non-contracting), which is not generically true.
Nevertheless, high dimensional expanders exhibit both good hitting set
behavior (see Proposition 10.12) and at least exponential degree (see
Proposition 9.6), so it is at least accurate to say double samplers arising
from HDX are at best quasi-polynomial in $\beta^{-1}$.

The proof of Theorem 9.3 relies on two further results. The first, toward our
upper bound, is Lubotzky, Samuels, and Vishne’s [LSV05a] classical
construction of Ramanujan complexes.

######  Theorem 9.4 (LSV-Complexes [LSV05a]).

For any $\lambda>0$ and $d\in\mathbb{N}$, there exists an explicit infinite
family of $d$-partite one-sided $\lambda$-local-spectral expanders
$\\{X^{(n)},\Pi^{(n)}\\}$ with degree
$\text{deg}(X)\leqslant\lambda^{-O(d^{2})}$. Moreover, for every $d\geqslant
k>\ell\geqslant 0$, $\max\\{\pi_{k}\\}\leqslant o_{n}(1)$.

The second, toward the lower bound, is the following optimality result we
prove in Section 11.1.

######  Corollary 9.5 (Corollary of Theorem 11.1).

For any $\varepsilon\in(0,0.01)$, let $X$ be a $d$-uniform,
$\frac{\varepsilon}{3}$-hitting vertex-uniform complex and $i\leqslant
k\leqslant d$. Then there exists a set $A\subset\X[i]$ such that:

$\operatorname*{\mathbb{P}}_{s\in\X[k]}[|U_{i,k}1_{A}(s)-\mu_{A}|>\varepsilon]\geqslant\exp\left(O\left(\varepsilon^{2}\frac{k}{i}\right)\right).$

We are now ready to prove Theorem 9.3.

###### Proof of Theorem 9.3.

We split into the upper and lower bounds.

##### Upper Bound

Let
$k=O\left(\frac{\log(1/\beta)\log(1/\beta_{0})}{\varepsilon^{2}\varepsilon_{0}^{2}}\right)$,
$d=k\log(k)$, and $\\{X_{n}\\}$ be an explicit infinite family of $d$-uniform
LSV-complexes with local-spectral expansion $\lambda=2^{-\Omega(d)}$, and take
$V_{2}=\X[k]$, $V_{1}=\X[i]$, and $V_{0}=\X[1]$ for
$i=\Theta(\frac{\log(1/\beta_{0})}{\varepsilon_{0}^{2}})$. By Theorem 5.1,
$(V_{2},V_{1})$ is an $(\varepsilon,\beta)$-sampler for the right choice of
constants. Moreover, every closure graph is simply the
$(\frac{\log(1/\beta_{0})}{\varepsilon_{0}^{2}})$-uniform complex on $k$
vertices, which is negatively correlated and therefore also a
$(\varepsilon_{0},\beta_{0})$-sampler by standard Chernoff-Hoeffding for
negatively correlated variables. The overhead bound is then immediate from the
degree of LSV complexes in Theorem 9.4.

##### Lower Bound

Recall that by definition $V_{0}^{(n)}=\X[1][n]=[n]$, $V_{1}^{(n)}=\X[i][n]$,
and $V_{2}^{(n)}=X_{n}(k)$ for some family of simplicial complexes
$\\{X_{n}\\}$ and set sizes $1<i<k$. By Corollary 9.5, for any
$\varepsilon\in(0,0.01)$, $(\X[k],\X[i])$ is at best an
$(\varepsilon,e^{O(\varepsilon^{2}\frac{k}{i})})$-sampler, therefore any such
double sampler requires:

$\frac{k}{i}\geqslant\Omega\left(\frac{\log(1/\beta)}{\varepsilon^{2}}\right).$

On the other hand, it is also required for every $T\in\X[k]$ that the induced
graphs $G|_{T}=(V_{2}|_{T},V_{1}|_{T})$ are
$(\varepsilon_{0},\beta_{0})$-samplers. By standard sampling lower bounds
[CEG95], this graph is at best a
$(\varepsilon_{0},e^{O(\varepsilon_{0}^{2}i)})$-sampler, forcing

$i\geqslant\Omega\left(\frac{\log(1/\beta_{0})}{\varepsilon_{0}^{2}}\right).$

Combining these bounds we have that for any valid choice of $i$ the top
uniformity $k$ of an $(\varepsilon,\beta,\varepsilon_{0},\beta_{0})$-double
sampler is at least

$k\geqslant\Omega\left(\frac{\log(\frac{1}{\beta})\log(\frac{1}{\beta_{0}})}{\varepsilon^{2}\varepsilon_{0}^{2}}\right).$

It is therefore enough to argue that the overhead is at least exponential in
the uniformity $k$:

$\frac{|V_{2}|}{|V_{0}|}\geqslant 2^{\Omega(k)}.$

This is true for any non-contracting complex. In particular, since
$|\X[k]|\geqslant|\X[k/2]|$, the average degree of every $(k/2)$-face (and
hence every vertex) is at least $2^{\Omega(k)}$. ∎ We remark that it may also
be possible to construct double samplers with smaller overhead by removing the
simplicial requirement from the definition (see e.g. the relaxed notion in
[DW22]). It is likely, for instance, that ‘Grassmannian HDX’ [KT21, Gol23,
DLZ23] based on subspace structure lead to double-samplers with different
parameters-overhead trade-offs.

###  9.2 A Degree Lower Bound for HDX

One of the most classical results in the study of expander graphs is the Alon-
Boppana Theorem [Nil91], roughly stating that any family of bounded-degree
$\lambda$-expanders must have degree at least $\frac{2}{\lambda^{2}}$. In
higher dimensions, the situation is less understood. Not only should degree
scale in some way with the local expansion $\lambda$, but dependence on
dimension becomes a critical parameter in application. In this section, we
give (to our knowledge) the first systematic study of the degree of high
dimensional expanders. In particular, we prove that various families of hyper-
regular HDX require super-exponential degree and prove a threshold-phenomenon
exists at the TD-barrier: there exist (reasonably balanced) constructions of
$1$-TD complexes achieving exponential degree at every level, while any
(reasonably balanced) $\lambda$-TD complex must have degree
$2^{-\Omega(k^{2})}$ for any level $k\leqslant\sqrt{d}$.

Before applying our stronger concentration bounds, we first look at what one
can infer about the degree of HDX directly from spectral methods. The
following proposition, though not to our knowledge appearing anywhere in the
literature, is the result of applying elementary spectral methods to the
problem:

######  Proposition 9.6 (Spectral Lower Bound).

Let $X$ be a $d$-uniform $\\{\lambda_{i}\\}$-two-sided local-spectral
expander. Then for every $k<d$, the degree of $X$’s $k$-skeleton is at least:

$\deg^{(k)}(X)\geqslant\frac{1}{(k-1)!}\prod\limits_{i=1}^{k-1}\frac{1}{\lambda_{i}}$

###### Proof.

Observe the $k$-th degree of a vertex $v\in\X[1]$ can be bounded by

$\frac{1}{(k-1)!}\prod_{i=1}^{k-1}\min_{t\in\X[i]}\\{|\X[1][t]|\\}$

simply by counting the number of ways a face
$\\{v_{2},\ldots,v_{k-1}\\}\in\SC[X][k][v_{1}]$ can be sampled by choosing
$v_{2}\sim\SC[X][1][v_{1}]$, $v_{2}\in\X[1][{\\{v_{1},v_{2}\\}}]$ and
correcting for the $\frac{1}{(k-1)!}$ possible orderings of the face. The
result now follows from the elementary fact (see e.g. [Gai+22, Lemma A.7])
that any two-sided $\lambda$-expander has at least $\frac{1}{\lambda}$
vertices. ∎

We remark that one might reasonably think to use Alon-Boppana [Nil91] (the
classic ‘optimal’ trade-off between expansion and degree) to prove a version
of the above for one-sided expansion. This does not work for high dimensional
expanders, since their links may have low diameter.

Proposition 9.6 implies that any (hyper-regular) $o(\frac{1}{d})$-two-sided
HDX must have super-exponential degree but is essentially trivial for
complexes near the TD-barrier, under spectral independence, or even for
arbitrarily strong partite one-sided HDX. In these cases, even if one is
willing to look e.g. at polynomial size cutoffs (as is quite common in the
literature) Proposition 9.6 only gives a slightly super-exponential lower
bound:

$\deg^{(k)}(X)\geqslant\exp(\Omega(k\log(k))).$

Using concentration, we improve this bound to strongly super-exponential. We
start with the partite case.

######  Theorem 9.7.

Fix $c\in[0,1]$ and let $X$ be a $d$-uniform hyper-regular partite
$2^{-\Omega(d^{c})}$-HDX. Then either:

  1. 1.

$X$’s 1-skeleton is dense:161616While this condition may seem strange, note it
is necessary to handle dense settings. Take, e.g., $\\{0,1\\}^{n}$, which is a
hyper-regular $0$-local-spectral expander whose $\sqrt{n}$-skeleton has degree
$\exp(\sqrt{n}\log(n))$.

$\deg^{1}(X)\geqslant\frac{|\X[1]|}{2}$

  2. 2.

$X$ has super-exponential degree:

$\deg^{(d)}(X)\geqslant\exp(\Omega(\max\\{d^{2c},d\\}))$

Second we prove an analogous bound for skeletons of TD and SI-complexes.

######  Theorem 9.8.

Let $\lambda,c\in[0,1)$, $\eta>0$, and $d\in\mathbb{N}$. If $X$ is a
$d$-uniform hyper-regular $\lambda$-TD or $\eta$-SI complex then for any
$k\leqslant d^{c}$:

  1. 1.

$X$’s 1-skeleton is dense:

$\deg^{1}(X)\geqslant\frac{|\X[1]|}{2}$

  2. 2.

$X$’s $k$-skeleton has super-exponential degree:

$\deg^{(k)}(X)\geqslant\exp(\Omega_{\lambda,\eta}(\min\\{k^{2},k^{1/c}\\}))$

The latter setting above is tight in the sense that when $\lambda=1$, that is
at the TD-barrier, there exist (reasonably balanced) complexes where
$\deg^{(k)}(X)=\exp(O(k))$ for all $k\leqslant d$. On the other hand, beyond
the TD barrier the best known degree upper bound for a hyper-regular (or even
reasonably balanced) HDX is $\exp(\exp(d))$ [FI20], leaving a substantial gap
with the above. Nevertheless, Theorem 9.8 is the first to exhibit quantitative
threshold behavior for degree at the TD-barrier.

Theorem 9.7 and Theorem 9.8 leave open two critical questions:

  1. 1.

Can we prove super-exponential bounds for the top level of a
$\lambda$-TD/$\eta$-SI complex?

  2. 2.

Can the assumption of hyper-regularity be dropped?

As we will see in the proof of Theorem 9.8, the first question would be
resolved if one could give any asymptotic improvement over exponential
concentration for weak HDX. In other words, any bound of the form:

$\operatorname*{\mathbb{P}}_{s\in\X[d]}\left[\frac{1}{d}|s\cap
A|-\mu>\frac{1}{2}\right]\leqslant\exp(\omega(\sqrt{d}))$

for $X$ and its links would imply a super-exponential degree lower bound. If,
for instance, we have a bound of $\exp(-\Omega(d))$ holds, this would imply a
degree lower bound of $\exp(\Omega(d^{2}))$ on the top level of $X$.

Regarding the second question, our proof technique extends to any complex
whose links are reasonably ‘balanced’ in the sense that there should not be a
$2^{-\Omega(\sqrt{d})}$ fraction of vertices making up an $\Omega(1)$ fraction
of the mass. Unfortunately, many classical HDX constructions, e.g. the
Ramanujan complexes of [LSV05a], actually are highly unbalanced in this sense.
The links of these constructions essentially approximate an ‘unbalanced
product’: they are partite complexes which are regular on each individual
part, but many of the parts are vanishingly small and therefore make up a
significant portion of the mass. While known constructions of this type all
have minimum part size at least exponential in $d$ (and therefore result in
degree $\exp(d^{2})$), it is unclear how to rule out a construction whose
links look, e.g., like $\\{0,1\\}^{d}\times[2^{d}]$. Such a complex could
potentially satisfy optimal inclusion sampling while maintaining exponential
degree.

We leave the possible extension of our lower bounds to the top level of
unbalanced complexes (or conversely the construction of highly locally
unbalanced exponential-size HDX) as one of the main open problems suggested by
this work:

######  Question 9.9 (Lower Bounds for Locally Unbalanced HDX).

Let $\\{X_{n}\\}$ be an infinite family of bounded-degree HDX that are either
$\lambda$-TD or $\eta$-SI. Is the degree of every (sufficiently large) $X_{n}$
super-exponential:

$\text{deg}(X_{n})\geqslant\exp(\omega(d))?$

Question 9.9 is critical from the standpoint of applying HDX in other areas of
theoretical computer science where degree dependence corresponds to the
‘overhead’ incurred by using the complex as a gadget. For instance, the lower
bound in Theorem 9.3 can be achieved by HDX essentially if and only if
Question 9.9 is false. Similarly, a variant of Question 9.9 where $d$ may
depend on $n$ is critical to the study of agreement testers whose soundness
scale with the _number of vertices_ of the system. Constructing polynomial
size testers with inverse polynomial soundness is the combinatorial core of
the so-called _sliding scale conjecture_ in PCP theory. If the above lower
bound holds, HDX cannot give such objects: $d$ must be taken to be
$o(\log(n))$ to maintain polynomial size, and the resulting soundness of any
HDX-based poly-size agreement tester would be at best $2^{-o(\log(n))}$,
missing the inverse polynomial mark.

We now move to the proofs of Theorem 9.7 and Theorem 9.8 which are inspired by
our localization technique for proving concentration that samples
$s=\\{v_{1},v_{1},\dots,v_{d}\\}$ by iteratively sampling $v_{0}\in X$, then
$v_{2}\in X_{v_{1}}$, $v_{3}\in X_{\\{v_{1},v_{2}\\}}$… and analyzing the
local concentration at each step. Upon further inspection, this technique
yields the fact that the $1$-skeleton of a complex with good sampling in $0$
and $1$-links must itself be an excellent sampler graph.

######  Lemma 9.10.

Fix $\varepsilon,\delta_{1},\delta_{2}>0$. Let $X$ be a $d$-uniform simplicial
complex such that:

  1. 1.

$(\X[d],\X[1])$ is a $(\frac{\varepsilon}{2},\delta_{1})$-additive sampler.

  2. 2.

For every $v\in\X[1]$, $(\SC[X][d][v],\SC[X][1][v])$ is an
$(\frac{\varepsilon}{2},\delta_{2})$-additive sampler.

Then the partite double cover of $X$’s $1$-skeleton is a
$(\varepsilon,\frac{2\delta_{1}}{1-\delta_{2}})$-sampler.

###### Proof.

Fix $A\subseteq\X[1]$. At a high level, the proof follows from observing that
if the base graph is a poor sampler, then after drawing the first vertex
$v_{1}$ of our $d$-set $t=\\{v_{1},\ldots,v_{d}\\}$, there is a non-trivial
chance that the neighborhood of $v_{1}$ (i.e. $\SC[X][1][v_{1}]$) ‘sees’ $A$
in the wrong proportion. However, since the remainder of the face
$\\{v_{2},\ldots,v_{d}\\}\in\SC[X][d][v_{1}]$, if
$(\SC[X][d][v_{1}],\SC[X][1][v_{1}])$ is indeed a good sampler it will
maintain this incorrect proportion from the first step and violate sampling of
$A$ in $(\X[d],\X[1])$.

We now formalize this argument. Given our assumptions we’d like to show:

$\operatorname*{\mathbb{P}}_{{v\in{\X[1]}}}\left[\operatorname*{\mathbb{P}}_{{u\in{\SC[X][1][v]}}}\left[A\right]>\operatorname*{\mathbb{P}}\left[{A}\right]+\varepsilon\right]\leqslant\frac{\delta_{1}}{1-\delta_{2}}.$

The lower tail follows from applying this on the complement set. Toward this
end, denote by $B$ the set of ‘bad’ vertices in $A$ that over-sample the base
graph:

$B=\left\\{v\in\X[1]\left|\;\vphantom{v\in\X[1]\operatorname*{\mathbb{P}}_{{u\in{\SC[X][1][v]}}}\left[A\right]>\operatorname*{\mathbb{P}}\left[{A}\right]+\varepsilon}\right.\operatorname*{\mathbb{P}}_{{u\in{\SC[X][1][v]}}}\left[A\right]>\operatorname*{\mathbb{P}}\left[{A}\right]+\varepsilon\right\\}.$

We need to show
$\operatorname*{\mathbb{P}}[B]\leqslant\frac{\delta_{1}}{1-\delta_{2}}$. We
bound $\operatorname*{\mathbb{P}}[B]$ by relating it to the set of bad
$d$-faces:

$C=\left\\{t\in\X[d]\left|\;\vphantom{t\in\X[d]\left\lvert\operatorname*{\mathbb{P}}_{{u\in
t}}\left[A\right]-\operatorname*{\mathbb{P}}\left[{A}\right]\right\rvert>\frac{\varepsilon}{2}}\right.\left\lvert\operatorname*{\mathbb{P}}_{{u\in
t}}\left[A\right]-\operatorname*{\mathbb{P}}\left[{A}\right]\right\rvert>\frac{\varepsilon}{2}\right\\},$

which has measure at most $\operatorname*{\mathbb{P}}[C]\leqslant\delta_{1}$
by Condition (2). The key to relate $B$ and $C$ is to observe we can sample a
random $d$-face $t$ by first sampling a vertex $v\in\X[1]$, then sampling $t$
from its link:

$\operatorname*{\mathbb{P}}\left[{C}\right]=\operatorname*{\mathbb{E}}_{{t\in{\X[d]}}}\left[{\mathbf{1}}_{C}(t)\right]=\operatorname*{\mathbb{E}}_{{v\in{\X[1]}}}\left[\operatorname*{\mathbb{E}}_{{t\in{\SC[X][d][v]}}}\left[{\mathbf{1}}_{C}(t)\right]\right]\geqslant\operatorname*{\mathbb{P}}\left[{B}\right]\operatorname*{\mathbb{E}}_{{v\in{\X[1]}}}\left[\operatorname*{\mathbb{E}}_{{t\in{\SC[X][d][v]}}}\left[{\mathbf{1}}_{C}(t)\right]\leavevmode\nobreak\
\Bigg{|}\leavevmode\nobreak\ v\in B\right].$

When $v\in B$, we have
$\operatorname*{\mathbb{P}}_{{u\in{\SC[X][1][v]}}}\left[A\right]\geqslant\operatorname*{\mathbb{P}}\left[{A}\right]+\varepsilon$
by assumption, but then by Condition (1)

$\operatorname*{\mathbb{E}}_{{v\in{\X[1]}}}\left[\operatorname*{\mathbb{E}}_{{t\in{\SC[X][d][v]}}}\left[{\mathbf{1}}_{C}(t)\right]\leavevmode\nobreak\
\Bigg{|}\leavevmode\nobreak\ v\in
B\right]\geqslant\operatorname*{\mathbb{P}}_{{t\in{\SC[X][d][v]}}}\left[\operatorname*{\mathbb{P}}\left[A\left|\;\vphantom{At}\right.t\right]>\operatorname*{\mathbb{P}}_{{u\in{\SC[X][1][v]}}}\left[A\right]-\frac{\varepsilon}{2}\right]\geqslant
1-\delta_{2}.$

Putting everything together we have

$(1-\delta_{2})\operatorname*{\mathbb{P}}\left[{C}\right]\leqslant\operatorname*{\mathbb{P}}\left[{B}\right]\leqslant\delta_{1}.$

and
$\operatorname*{\mathbb{P}}\left[{C}\right]\leqslant\frac{\delta_{1}}{1-\delta_{2}}$
as desired. ∎

Combining this fact with standard degree lower bounds for sampler graphs
[CEG95] gives the following degree lower bound for the 1-skeletons of such
complexes:

######  Corollary 9.11.

Let $X$ be a $d$-uniform simplicial complex satisfying:

  1. 1.

$(\X[d],\X[1])$ is a $(\frac{1}{10},\delta_{1})$-sampler

  2. 2.

For all $v\in\X[1]$, $(\SC[X][d][v],\SC[X][1][v])$ is a
$(\frac{1}{10},\delta_{2})$-sampler.

Then $X$’s $1$-skeleton has high max-degree:

$\exists
v\in\X[1]:\deg^{(1)}(v)\geqslant\min\left\\{\frac{|\X[1]|}{2},\frac{2(1-\delta_{2})}{5\delta_{1}}\right\\}$

###### Proof.

By Lemma 9.10 the underlying graph of $X$ is a
$(\frac{1}{5},\delta=\frac{2\delta_{1}}{1-\delta_{2}})$-sampler. [CEG95,
Theorem 2] states the following relation on a graph $G=(L,R,E)$ that is an
$(\varepsilon,\delta)$-sampler of max degree $t\leqslant\frac{|\X[1]|}{2}$.

$t|R|\geqslant\frac{|L|(1-2\varepsilon)}{2\delta}.$

Here $L=R=\X[1]$ and this inequality gives
$t\geqslant\frac{0.8}{2\delta}=\frac{2(1-\delta_{2})}{5\delta_{1}}$. ∎

Notice this bound is substantially stronger than what can be inferred from
spectral expansion alone. For instance, when $X$ is a
$\lambda=\operatorname{poly}(d^{-1})$-HDX, Alon-Boppana only implies a degree
lower bound of $\Omega(\lambda^{-2})=\operatorname{poly}(d^{-1})$, whereas
combining the above with Corollary 7.7 gives degree at least
$\exp(-\sqrt{d})$. Given this fact, Theorem 9.7 and Theorem 9.8 follows by
recursive application of Corollary 9.11 on each link of the HDX.

###### Proof of Theorem 9.7 and Theorem 9.8.

Similar to the spectral argument, since $X$ is hyper-regular the $k$th degree
of any vertex $v_{0}\in\X[1]$ can be bounded by:

$\deg^{(k)}(v_{0})\geqslant\frac{1}{(k-1)!}\prod\limits_{i=1}^{k-1}\min_{t\in\X[i]}\left\\{\deg^{(1)}(X_{t})\right\\}.$

It is therefore sufficient to bound the degree of the 1-skeleton of the links
of $X$. We split the analysis into the partite and TD/SI cases.

##### Partite Case

Let $k^{\prime}=\max\\{\sqrt{d},d^{c}\\}$. By Theorem 7.1, there exists a
universal constant $c^{\prime}>0$ such that for every $t\in
X^{\leqslant\frac{d}{2}}$, the link $X_{t}$ satisfies:

  1. 1.

$(\X[d-|t|][t],\X[1][t])$ is a
$(\frac{1}{10},\exp(-c^{\prime}k^{\prime}))$-sampler

  2. 2.

For all $v\in\SC[X][1][t]$,
$(\SC[X][d-|t|-1][t\cup\\{v\\}],\X[1][t\cup\\{v\\}])$ is a
$(\frac{1}{10},\exp(-c^{\prime}k^{\prime}))$-sampler.

Setting $t\in\X[1]$, Corollary 9.11 implies

$\deg^{(1)}(X)\geqslant\min\left\\{\frac{|\X[1]|}{2},\exp(-c^{\prime}k^{\prime})\right\\}.$

Assume $\exp(-c^{\prime}k^{\prime})\leqslant\frac{|\X[1]|}{2}$ (else Condition
(1) is satisfied and we are done). Under this assumption, we argue by
induction that the max degree of any $i$-link is at least:

$\forall
i\leqslant\frac{d}{2}:\;\;\min_{t\in\X[i]}\\{\deg^{(1)}(X_{t})\\}\geqslant\frac{1}{2^{i}}\exp(c^{\prime}k^{\prime}).$
(9.1)

We remark the restriction on $i$ is to enforce that links of this level are
still $(\frac{1}{10},\exp(-c^{\prime}k^{\prime}))$-samplers. Plugging this
back into our bound on degree gives $\exp(-\Omega(k^{\prime
2}))\geqslant\exp(-\Omega(\max\\{d,d^{2c}\\}))$ as desired.

To prove (9.1), observe the base case $i=1$ is given by assumption. The
inductive step simply follows from observing that the minimum number of
vertices in any $i$-link is exactly the minimum degree of the 1-skeleton of
any $(i-1)$-link. Thus applying Corollary 9.11, we have:

$\forall
t\in\X[i]:\deg^{(1)}(X_{t})\geqslant\min\left\\{\frac{|\X[1][t]|}{2},\exp(-c^{\prime}k^{\prime})\right\\}\geqslant\frac{1}{2^{i}}\exp(c^{\prime}k^{\prime}).$

as desired.

##### TD/SI Case

When $X$ is $\lambda$-TD or $\eta$-SI, we’d like to run the same argument as
above but run into a slight problem. We can still bound the $k$th degree of a
vertex $v$ by:

$\deg^{(k)}(v)\geqslant\frac{1}{(k-1)!}\prod\limits_{i=1}^{k-1}\min_{t\in\X[i]}\left\\{\deg^{(1)}(X_{t})\right\\},$

but because $X$ satisfies only exponential concentration, (9.1) becomes

$\forall
i\leqslant\frac{d}{2}:\min_{t\in\X[i]}\\{\deg^{(1)}(X_{t})\\}\geqslant\frac{1}{2^{i}}\exp(c^{\prime}\sqrt{d}).$

This bound is now only non-trivial up to $i\leqslant O(\sqrt{d})$ levels of
$X$, stopping us from proving super-exponential concentration for $X$’s top
level. Nevertheless, when $k=d^{c}$, plugging the above into the degree
calculation gives $\exp(d)=\exp(k^{1/c})$ whenever $c\geqslant 1/2$, and
$\exp(k\sqrt{d})\geqslant\exp(k^{2})$ whenever $c<1/2$. ∎

###  9.3 Geometric Overlap

The geometric overlap property is a classical notion of high dimensional
expansion (see e.g. [Lub18]) which promises every embedding of the complex has
a point in space hit by at least a constant fraction of the faces.

######  Definition 9.12.

Let $X$ be a $d$-uniform simplicial complex and let $k\leqslant d-1$. Let
$c>0$. We say that $X$ has $(k,c)$-geometric overlap if for every
$\rho:\X[1]\to\mathbb{R}^{k}$, there exists a point $q_{0}\in\mathbb{R}^{k}$
such that

$\operatorname*{\mathbb{P}}_{{s\in{\X[d]}}}\left[q_{0}\in
conv(\rho(s))\right]\geqslant c.$

Here $conv(\rho(s))$ is the convex hull of the points of
$\rho(s)=\left\\{\rho(v)\left|\;\vphantom{\rho(v)v\in s}\right.v\in
s\right\\}$. While we are not aware of any applications of geometric overlap
in computer science, it is a popular topic in geometry and topology and
related ideas (e.g. an overlap variant of the Borsuk-Ulam theorem) have seen
recent use in the study of algorithmic stability [Cha+23].

Boros and Füredi [BF84] showed that the $2$-dimensional complete complex has
geometric overlap, a result which was later generalized to all dimensions by
Bárány [Bár82]. The notion was extended to general simplicial complexes by
Gromov [Gro10], who asked whether there are bounded degree complexes that have
this property. Followup work by Fox, Gromov, Lafforgue, Naor, and Pach
[Fox+12] gave an affirmative answer to this question both via random
construction and through [LSV05]’s Ramanujan complexes. Finally, a series of
works [PRT16, Evr17, Opp18] extended their ideas to general spectral high
dimensional expanders by leveraging high dimensional expander-mixing
properties. We note that Gromov also defined a closely related (but stricter)
notion of topological overlap [Gro10], which was later studied by [KKL14,
EK16] among others. We focus only on the geometric setting here.

While prior works have succeeded in showing optimal geometric overlap for
random bounded-degree complexes [Fox+12, Theorem 1.7], it has been open since
Gromov’s work to construct such a family explicitly. In this subsection,
building on the approach of these prior works, we show sufficiently strong
high dimensional expanders have optimal overlap, resolving this problem.

To state our result, it is useful to first understand the overlap properties
of the complete complex. Let $c_{k,n}$ be the largest constant so that
$\SC[\Delta][k+1][n]$ has $(k,c_{k,n})$-geometric overlap, and let
$c(k)=\lim_{n\to\infty}c_{k,n}$. By [Bár82] this limit exists and is positive.
Similarly, let $c_{d,k,n}^{p}$ be the largest constant so that the complete
$d$-partite complex with $n$-vertices on every side has
$(k,c_{d,k,n}^{p})$-geometric overlap, and let
$c_{d,k}^{p}=\lim_{n\to\infty}c_{d,k,n}^{p}$. Existence and positivity of this
limit follows from [Pac98]. The former constant, $\SC[c][k]$, is known to be
the best possible for bounded degree simplicial complexes [Fox+12, Theorem
1.6].

We show that every sufficiently strong (partite) high dimensional expanders
has geometric overlap nearly matching the (partite) complete complex:

######  Theorem 9.13.

For every $\varepsilon>0$ and $k<d\in\mathbb{N}$, there exist
$\lambda,\lambda_{p}>0$, and $n_{0},n_{0,p}\in\mathbb{N}$ such that

  1. 1.

Two-sided case: If $X$ is $d$-uniform $\lambda$-two-sided high dimensional
expander on at least $n_{0}$ vertices so that the measure on the vertices is
uniform, then $X$ has $(k,c_{k}-\varepsilon)$-geometric overlap.

  2. 2.

Partite case: If $X$ is $d$-partite $\lambda_{p}$-one-sided HDX on at least
$n_{0,p}$ vertices so that the measure on the vertices is uniform, then $X$
has $(k,c^{p}_{d,k}-\varepsilon)$-geometric overlap.

We comment that this theorem applies to many of the complexes constructed in
[LSV05] (for the non-partite setting we need to take lower uniform skeletons).

The proof of Theorem 9.13 combines our concentration bounds with tools
developed in [Fox+12]. We have not tried to find the optimal dependence on
$\lambda$ or on the degree of the complex. Finally before moving to the proof,
we remark that the result really only relies on the weaker ‘high-dimensional
expander-mixing’ type inequality which actually holds for the more general
family of splitting-trees such as expander walks (see Section 10.1). Thus it
is possible to obtain explicit complexes with geometric overlap approaching
that of the complete (partite) complex through this more general family as
well, though we omit the details.

##### Homogeneous tuples

The core of [Fox+12]’s proof of geometric overlap is the following
partitioning theorem. We follow their definitions and presentation precisely.
A tuple of subsets $S_{1},\ldots,S_{k+1}\subseteq\mathbb{R}^{k}$ is said to be
_homogeneous_ with respect to a point $q\in\mathbb{R}^{k}$ if either:

  1. 1.

All simplices with one vertex in each of the sets $S_{1},\ldots,S_{k+1}$
contain $q$.

  2. 2.

None of these simplices contain $q$.

An _equipartition_ of a finite set is a partition of the set into subsets
whose sizes differ by at most one.

######  Theorem 9.14 ([Fox+12, Corollary 1.9]).

Let $d$ be a positive integer and $\varepsilon>0$. There exists a positive
integer $K=K(\varepsilon,k)\geqslant k+1$ such that for any
$K^{\prime}\geqslant K$ the following statement holds. For any finite set
$P\subseteq\mathbb{R}^{k}$ and for any point $q\in\mathbb{R}^{k}$, there is an
equipartition $P=P_{1}\mathbin{\mathaccent
0{\cdot}\cup}\dots\mathbin{\mathaccent 0{\cdot}\cup}P_{K^{\prime}}$ such that
all but at most an $\varepsilon$-fraction of the $(k+1)$-tuples
$P_{i_{1}},\ldots,P_{i_{k+1}}$ are homogeneous with respect to $q$.

Our proof adapts the idea in [Fox+12, Theorem 1.7].

###### Proof of Theorem 9.13.

We split the proof into the two-sided and partite cases.

##### Two-sided Case

Let $K=K(\varepsilon/16,k)$ be the constant promised in Theorem 9.14 and
$K^{\prime}\geqslant K$ be the smallest constant so that for any equipartition
of the $n$-vertices to $K^{\prime}$ parts, the fraction of faces in the
complete complex (over the same vertex set) that touch every part at most once
is at least $1-\frac{\varepsilon}{16}$.171717One can verify as in [Fox+12,
Theorem 1.7] that $K^{\prime}=\max\\{K,16(d+1)/\varepsilon\\}$ for large
enough $n$. Let $z_{0}=\frac{1}{2K^{\prime}}$ and let $n_{0}$ be such that for
any $n\geqslant n_{0}$ and sets $A_{1},A_{2},\dots,A_{k+1}\subset[n]$ of
measure at least $\frac{1}{K^{\prime}}-z_{0}$ it holds that

$\operatorname*{\mathbb{P}}_{{\\{v_{1},v_{2},\dots,v_{k+1}\\}\in{\SC[\Delta][k+1][n]}}}\left[\forall
j=0,1,\dots,d:\leavevmode\nobreak\ v_{j}\in
A_{j}\right]\geqslant\prod_{j=1}^{k+1}\operatorname*{\mathbb{P}}\left[{A_{j}}\right]-\frac{\varepsilon}{16}.$

Let $X$ be as in the statement and $\rho:\X[1]\to\mathbb{R}^{k}$ an embedding.
There is a point $q_{0}\in\mathbb{R}^{k}$ so that $q_{0}$ is contained in
$c_{k}-\frac{\varepsilon}{16}$ of the faces of $\SC[\Delta][k+1][n]$ embedded
via $\rho$.

Let $P_{1},P_{2},\dots,P_{K^{\prime}}$ be the partition we obtain from Theorem
9.14 with respect to $\rho$ and the complete complex. Let
$H=\left\\{\\{P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}}\\}\left|\;\vphantom{\\{P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}}\\}\forall
s\in E(P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}}),\;q_{0}\in
conv(\rho(s))}\right.\forall s\in
E(P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}}),\;q_{0}\in conv(\rho(s))\right\\}$.
Here $E(P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}})$ are the faces $s\in\X[k]$ such
that for every $j=1,\dots,k+1$, $\left\lvert s\cap P_{i_{j}}\right\rvert=1$.
Recall that at most an $\frac{\varepsilon}{16}$-fraction of the tuples are not
homogeneous and that at most $\frac{\varepsilon}{16}$ of the faces in
$\SC[\Delta][k+1][n]$ touch a part in this partition more than once. Thus,

$\sum_{(P_{i_{j}})_{j=1}^{k+1}\in
H}\prod_{j=1}^{k+1}\operatorname*{\mathbb{P}}\left[{P_{i_{j}}}\right]\geqslant
c_{k}-\frac{3\varepsilon}{16}.$ (9.2)

On the other hand,

$\operatorname*{\mathbb{P}}_{{s\in{\X[k+1]}}}\left[q_{0}\in
conv(\rho(s))\right]\geqslant\sum_{\\{P_{i_{1}},P_{i_{1}},\dots,P_{i_{k+1}}\\}\in
H}{\operatorname*{\mathbb{P}}_{{s\in{\X[k+1]}}}\left[E(P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}})\right]}.$
(9.3)

By Proposition 7.2 (applied for indicators of the corresponding functions) for
small enough $\lambda=\lambda(K^{\prime},\varepsilon,z_{0})$, for every $k+1$
parts $P_{i_{1}},P_{i_{2}},\dots,P_{i_{k+1}}$ of size at least
$\frac{1}{K^{\prime}}-z_{0}$,

$\operatorname*{\mathbb{P}}_{{\\{v_{1},v_{2},\dots,v_{k+1}\\}\in{\X[k+1]}}}\left[\forall
j=1,\dots,k+1\;v_{j}\in
P_{i_{j}}\right]\geqslant(1-\frac{\varepsilon}{2})\prod_{j=1}^{k+1}\operatorname*{\mathbb{P}}\left[{P_{i_{j}}}\right].$

Combining (9.2) and (9.3) gives
$\operatorname*{\mathbb{P}}_{{s\in{\X[k+1]}}}\left[q_{0}\in\rho(s)\right]\geqslant(1-\frac{\varepsilon}{2})(c_{k}-\frac{\varepsilon}{4})\geqslant
c_{k}-\varepsilon$ as desired.

##### Partite Case

The argument is similar. Let $K=K(\varepsilon/16,k)$ be the constant promised
in Theorem 9.14. Let $K^{\prime}\geqslant K$ be the smallest constant so that
for any equipartition over $K^{\prime}$ parts, the fraction of faces in the
complete partite complex that touch every part at most once is at least
$1-\frac{\varepsilon}{16}$.

Let $z=\frac{1}{2K^{\prime}}$ be as before. As before we first identify the
points of $X$ with the complete partite complex with the same number of
vertices in every side. Then we find a point $q_{0}$ such that
$c_{d,k}^{p}-\frac{\varepsilon}{16}$ of the faces of the complete partite
complex contain $q_{0}$. We find an equipartition
$P_{1},P_{2},\dots,P_{K^{\prime}}$ of $\rho(\X[1])$ to $K^{\prime}$ parts such
that $1-\frac{\varepsilon}{16}$ of the parts are homogeneous with respect to
$q_{0}$.

We partition further every $P_{i}$ according to the colors of the vertices to
$P_{i}^{j}$ for $j=1,2,\dots,d$. Then we remove from the partition every
subset $P_{i}^{j}$ whose relative size is smaller than
$\frac{\varepsilon}{16K^{\prime}\cdot d^{2}}$. We note that by taking only the
remaining sets in the partition the fraction of vertices we removed from every
color is no more than $\frac{\varepsilon}{8}$ vertices in any side. This is
because for every $P_{i}$, colors $j$ that have that
$\operatorname*{\mathbb{P}}\left[{P_{i}^{j}}\right]\leqslant\frac{\varepsilon}{16K^{\prime}\cdot
d^{2}}$ can account for no more than $\frac{\varepsilon}{16K^{\prime}\cdot d}$
out of at least $\frac{1}{K^{\prime}}-z=\frac{1}{2K^{\prime}}$. Thus we have
not removed more than $\frac{\varepsilon}{8d}$ vertices in total, or
$\frac{\varepsilon}{8}$-fraction out of each color.

We now have subsets $P_{i}^{j}$ that such that
$\frac{\varepsilon}{16K^{\prime}d^{2}}\leqslant\operatorname*{\mathbb{P}}\left[{P_{i}^{j}}\right]\leqslant\frac{3}{2K^{\prime}}$.
The proof now follows as in the two-sided case. ∎

###  9.4 Separating MLSI from Reverse Hypercontractivity

As discussed in Section 1, prior techniques for establishing reverse
hypercontractivity relied on tensorization or bounded (Modified) Log-Sobolev
constant (MLSI). To our knowledge, all known reverse-hypercontractive objects
prior to this work also have bounded MLSI. In this section, we give the first
separation between these analytic notions in the case where the leading
hypercontractive constant $C$ may be greater than $1$ (or, alternatively, for
the indicator variant). To start, recall the definition of MLSI.

######  Definition 9.15 (Modified Log-Sobolev Inequality).

Let $M$ be a reversible markov chain with stationary distribution $\pi_{s}$.
The modified log-sobolev constant of $M$ is:

$\rho_{\text{\tiny{MLSI}}}=\inf_{f>0}\frac{\langle f,(I-M)\log
f\rangle}{2\text{Ent}_{\pi}(f^{2})}$

MLSI is classically used to bound the mixing time of its associated Markov
chain,

$T_{\text{mix}}(M,\varepsilon)=\min_{t}\max_{\pi_{init}}\lVert\pi_{init}^{T}M^{t}-\pi_{s}\rVert_{TV}\leqslant\varepsilon,$

due to the following upper bound:

######  Fact 9.16.

The mixing time of a reversible Markov chain $M$ with stationary distribution
$\pi$ is at most:

$T_{\text{mix}}(M,\varepsilon)\leqslant\frac{1}{\rho_{\text{\tiny{MLSI}}}}\log\left(\frac{\log\pi_{*}^{-1}}{\varepsilon}\right),$

where $\pi_{*}$ is the minimum stationary probability

High dimensional expanders (at least in the bounded degree setting), are slow-
mixing, so they cannot have small MLSI constant. In particular, applying this
fact to the Ramanujan complexes gives an infinite family of reverse-
hypercontractive operators with at least inverse logarithmic dependence on the
domain size.

######  Corollary 9.17.

There exist constants $\ell>1$ and $C>0$ and an infinite family
$\\{T_{\rho}^{(n)}\\}$ of $(\frac{1}{\ell},\frac{\ell}{1-\ell},C)$-reverse
hypercontractive operators with at most inverse logarithmic MLSI:

$\rho_{MLSI}\leqslant C_{2}\frac{\log^{3}\log(\pi_{*})}{\log\pi_{*}}$

###### Proof.

Set $\rho=\frac{1}{2}$, let $c$ be as in Theorem 6.3, and let $\\{X^{(n)}\\}$
be the family of $k=k(n)$-uniform cut-off coset complexes promised in Theorem
9.4 for $k=\log\log n$ and $\lambda=2^{-k}$, and recall that

  1. 1.

The degree of every vertex is at most $2^{C_{2}k^{3}}$ for some universal
constant $C_{2}>0$

  2. 2.

The stationary distribution of $T_{1/2}$ on $X$ is uniform

By Theorem 6.3, there exist (universal) constants $C,\ell$ such that the noise
operator $T_{1/2}$ is $(\frac{1}{\ell},\frac{\ell}{1-\ell},C)$-reverse
hypercontractive for every complex in the family. On the other hand, we will
argue that:

$T_{\text{mix}}\left(T_{\rho},\frac{1}{2}\right)\geqslant\min\left\\{\frac{2^{k}}{4},\frac{C^{\prime}_{2}\log(n)}{k^{3}}\right\\},$

which combined with Fact 9.16 completes the result.

Define the $\varepsilon$-support of a distribution

$\text{supp}^{\geqslant}_{\varepsilon}(\pi)\coloneqq\\{x:\pi(x)\geqslant\varepsilon\\}.$

Setting $\varepsilon=\frac{1}{4n}$, observe that any distribution $\pi$ with
$|\text{supp}^{\geqslant}_{\varepsilon}(\pi)|<\frac{n}{4}$ has
$\lVert\pi-\pi_{s}\rVert_{TV}\geqslant\frac{1}{2}$. We will argue this holds
for $\pi_{\text{init}}T_{\frac{1}{2}}^{t}$ whenever $\pi_{\text{init}}$ is any
indicator and $t$ is sufficiently small.

To see this, we separate out the bounded-degree and stationary components of
$T_{\frac{1}{2}}$ as:

$T_{\frac{1}{2}}^{+}\coloneqq T_{\frac{1}{2}}-2^{-k}\Pi$

where $\Pi$ is the stationary operator, and note that
$T_{\frac{1}{2}}=T_{\frac{1}{2}}^{+}+2^{-k}\Pi$. Observe that after $t$ steps,
we can write any initial distribution $\pi$ as:

$\pi^{T}T_{\frac{1}{2}}^{t}=\pi^{T}(T^{+}_{\frac{1}{2}}+2^{-k}\Pi)^{t}=\pi^{T}(T^{+}_{\frac{1}{2}})^{t}+(1-(1-2^{-k})^{t})\pi_{s}$

For large enough $k$, as long as $t\leqslant 2^{-k/4}$, the latter term
contributes strictly less than $\frac{1}{4}$ to each coordinate. On the other
hand for $\pi$ an indicator, the first term contributes positive weight to at
most $deg(T_{\frac{1}{2}^{+}})^{t}$ coordinates, so setting $t$ such that
$deg(T_{\frac{1}{2}^{+}})^{t}\leqslant\frac{n}{4}$ completes the result. ∎

###  9.5 It Ain’t Over Till It’s Over

Friedgut and Kalai’s ‘It Ain’t Over Till It’s Over’ Theorem is a classical
result in social choice which states that even after taking a significant
random restriction, any balanced function still has some uncertainty with high
probability (in other words, it is a tail bound on the random restriction
operator). The precursor to this Theorem was a version for the noise operator
proved in [MOO05, Appendix C]. We prove the result holds for any LUS, which
implies the same for any $c$-nice complex.

######  Theorem 9.18.

For any $\rho\in(0,1)$ and $\tau>0$, let $X$ be a $d$-uniform $\tau$-LUS for
$d$ sufficiently large. Then there exists a constant $q=q(\rho,\tau)$ such
that for any $\delta>0$ and $f:\X[d]\to[0,1]$ with density
$\mu=\mathbb{E}[f]$:

$\operatorname*{\mathbb{P}}[T_{\rho}f>1-\delta]\leqslant c_{\mu,1}\delta^{q}$

where
$c_{\mu,1}=\left(\frac{8(1+\mu)^{q+1}}{(1-\mu)^{q+2}}\right)^{\frac{1}{q}}$,
and

$\operatorname*{\mathbb{P}}[T_{\rho}f<\delta]\leqslant c_{\mu,2}\delta^{q}$

where $c_{\mu,2}=\left(\frac{8(2-\mu)^{q+1}}{\mu^{q+2}}\right)^{\frac{1}{q}}$.

###### Proof.

We prove the former. The latter follows from considering $1-f$. Let $T$ of the
set of elements whose neighborhoods are dense in $f$:

$T\coloneqq\\{x:T_{\rho}f(x)\geqslant 1-\delta\\},$

and consider the indicator cut-off $h=\mathbf{1}_{f\leqslant\frac{1+\mu}{2}}$.
We will argue that on the one hand the correlation of $T$ and $h$ cannot be
large, since when $x\in T$, $y\sim_{\rho}x$ must be mostly above the cutoff.
On the other hand, the correlation is at least some power of $\mu(T)$ by
reverse hypercontractivity, so $\mu(T)$ must be small.

Formally, observe that for any $x\in T$, Markov’s inequality gives that
$T_{\rho}h(x)\leqslant\frac{2\delta}{1-\mu}$ so

$\mathbb{E}[1_{T}T_{\rho}h]\leqslant\mu(T)\delta\frac{2}{1-\mu}.$

On the other hand, we also have by Markov that
$\mathbb{E}[h]\geqslant\frac{1-\mu}{1+\mu}$, so reverse hypercontractivity for
indicators (Theorem 6.4) implies there exists some $\ell$ such that:

$\mathbb{E}[1_{T}T_{\rho}h]\geqslant\frac{1}{4}\left(\mu(T)\frac{1-\mu}{1+\mu}\right)^{\ell}$

Combining the equations and setting $q=\ell-1$ gives the desired result. ∎

We note we have made no attempt to optimize the constants, and it may be
possible to improve dependence on $\mu$. [MOO05] combine a variant of Theorem
9.18 with the invariance principle to prove the classical form of the
conjecture with respect to random restrictions. It is not clear what the
correct form of this conjecture should be for HDX, or even for product
spaces.181818We remark it should be possible to give a version of the result
for suitably ‘global’ functions via tools of [Kee+21, GLL22, Baf+22a], but it
is not clear such a notion would have significant qualitative meaning We leave
this as an open question.

###  9.6 A Frankl–Rödl Theorem

The Frankl–Rödl Theorem [FR87] is a powerful result from extremal
combinatorics that states that the independence number of the graph whose
vertices are $\\{0,1\\}^{n}$ and whose edges are given by fixed weight
intersection $k$ (typically for some $k=\Theta(n)$) is at most
$\exp(-\Omega(k))|V|$. Benabbas, Hatami, and Magen [Ben12] proved a variant of
this Theorem via reverse hypercontractivity on the cube, later leading to
several applications in hardness of approximation [Kau+14]. Their method,
which also bounds classical properties such as the chromatic and dominating
set numbers, is based on the following claim:

######  Claim 9.19.

Let $p_{0},q_{0}>0$ and let $G=(V,E)$ be a weighted graph with minimum vertex
weight $q_{0}$ such that for every $A,B\subset V$ of relative size at least
$p_{0}$:

$\operatorname*{\mathbb{P}}_{{(s_{1},s_{2})\sim E}}\left[s_{1}\in A,s_{2}\in
B\right]>0.$

Then the maximal independent set in $G$ has size at most $2p_{0}+q_{0}$, the
minimal dominating set has relative size at least $1-(2p_{0}+q_{0})$, and the
chromatic number is at least $\frac{1}{2p_{0}+q_{0}}$.

As a corollary we have that the down-up walks in any of the discussed LUS-
complexes in Section 6.3 have maximal independent sets of relative size at
most $\exp(-\Omega(k))$, a chromatic number of at least $\exp(\Omega(k))$ and
minimal dominating sets of size at least $1-\exp(-\Omega(k))$. As discussed in
the introduction, we remark that these graphs are not quite the correct analog
of Frankl–Rödl, since they have edges with intersection up to some fixed
$\gamma k$ instead of $\gamma k$ exactly. Benabbas, Hatami and Magen [Ben12]
handle this by analyzing the closeness of the exact intersection versus noise
operator on the cube, using tools from Fourier analysis. It would be
interesting to see if a variant of this result holds on HDX. If this could be
shown generally, then our reverse hypercontractivity theorem would recover
Frankl–Rödl up to constants in the exponent.

###### Proof of Claim 9.19.

We prove the statement for independent sets. The chromatic number statement
follows since every coloring is a partition to independent sets, and the
statement for dominating sets follows since the complement of any dominating
set is an independent set. Let $I\subseteq G$ be an independent set and assume
toward contradiction that $\operatorname*{\mathbb{P}}\left[{I}\right]\geqslant
2p_{0}+q_{0}$. We partition $I$ into $I_{1},I_{2}$ such that
$\operatorname*{\mathbb{P}}\left[{I_{1}}\right],\operatorname*{\mathbb{P}}\left[{I_{2}}\right]\geqslant
p_{0}$ (we can do so by greedily adding vertices to $I_{1}$ until its
probability is between $p_{0}$ and $p_{0}+q_{0}$). Then by assumption
$\operatorname*{\mathbb{P}}_{{(s_{1},s_{2})\sim E}}\left[s_{1}\in
I_{1},s_{2}\in I_{2}\right]>0$, which gives the desired contradiction. ∎

######  Remark 9.20.

Although the graphs we discussed in this paper have self loops. The claim
above continues to hold after removing these self loops, as is evident from
the proof.

##  10 Codes and Splitting Trees

Error correcting codes, and in particular the powerful notions of list-
decoding and local-testability, are among the earliest successful applications
of inclusion samplers [Imp+08, IJK09, IKW12] and HDX [Din+18, Ale+20, JST21,
PK22, Din+22]. In this section we explore the implications of our tools and
related ideas over the weaker family of ‘splitting trees’ in this classical
setting. Our main application is the first construction of constant rate codes
over large alphabets which simultaneously have 1) near-optimal distance 2)
list-decodability and 3) local-testability. At the end of the section we
introduce a (conjectural) HDX-based approach toward ‘lossless’ distance-
amplification of LTCs that experiences no decay in soundness.

###  10.1 Splitting Trees

We start with a fairly substantial detour into the world of splitting trees,
which are a weakening of high dimensional expanders introduced in [AJT19]
which only requires certain patterns of swap walks to expand. We will prove a
high-dimensional expander mixing lemma and some basic sampling properties for
general splitting trees that will be useful for our applications to coding
theory.

####  10.1.1 Splitting Preliminaries

Given a binary tree $T$, let $\mathcal{L}(T)$ denote $T$’s leaves and
$\mathcal{I}(T)$ its internal nodes. We drop $T$ from the notation when clear
from context. For every internal node $v\in\mathcal{I}$, denote the left and
right children of $v$ by $\ell_{u}$ and $r_{u}$ respectively.

######  Definition 10.1 (Ordered Binary Tree).

A $d$-uniform ordered binary tree is a pair $(T,\rho)$ where $T$ is a rooted
binary tree with $d$ leaves, and $\rho:T\to[d]$ is a labeling such that:

  1. 1.

The label of every leaf $u\in\mathcal{L}$ is $\rho(u)=1$.

  2. 2.

For every interior $u\in\mathcal{I}$, it holds that
$\rho(u)=\rho(\ell_{u})+\rho(r_{u})$.

We call such a $\rho$ well-ordered with respect to $T$.

A complex is called splittable if it can be decomposed by an ordered tree
where every non-leaf node corresponds to an expanding swap walk.

######  Definition 10.2 (Splitting tree).

Let $\gamma>0$. A $d$-uniform  _$\gamma$ -splitting tree_ is a triple
$(X,T,\rho)$ where $X$ is a $d$-uniform simplicial complex and $(T,\rho)$ is
an ordered binary tree such that for every $u\in\mathcal{I}(T)$:

$\lambda(S_{\rho(\ell_{u}),\rho(r_{u})})\leqslant\gamma,$

We will also work with the corresponding partite notion of splitting trees.

######  Definition 10.3 (Partite Ordered Binary Tree).

A $d$-uniform partite ordered binary tree is a pair $(T,\rho)$ where $T$ is a
rooted binary tree with $d$ leaves, and
$\rho:T\to\mathbb{P}\\{[d]\\}\setminus\\{\emptyset\\}$ is a labeling such
that:

  1. 1.

$\rho|_{\mathcal{L}}$ is a bijection to the singletons of $[d]$.

  2. 2.

For every interior $u\in\mathcal{I}$, it holds that
$\rho(u)=\rho(\ell_{u})\mathbin{\mathaccent 0{\cdot}\cup}\rho(r_{u})$.

We remark that when convenient, we may use a general set $S$ of size $d+1$ as
the domain of $\rho$ (generally corresponding to a labeling of the "parts" of
an associated $d$-uniform partite complex).

######  Definition 10.4 (Tuple splitting tree).

Let $\gamma>0$. A $d$-uniform  _$\gamma$ -tuple splitting tree_ is a triple
$(X,T,\rho)$ where $X$ is a $d$-uniform simplicial complex and $(T,\rho)$ is
an ordered partite binary tree such that for every non-leaf vertex $u\in T$:

$\lambda(S_{\rho(\ell_{u}),\rho(r_{u})})\leqslant\gamma$

Since all swap walks on two-sided HDX expand, these give rise to a basic
family of splitting trees.

######  Example 10.5 ([AJT19, DD19, GLL22]).

Let $\lambda\geqslant 0$ and let $X$ be a $d$-uniform two-sided $\lambda$-high
dimensional expander. Then for any binary tree $T$ and labeling $\rho$ that
satisfies the first and second item in Definition 10.2, $(X,T,\rho)$ is a
$d\lambda$-splitting tree.

An easy consequence of [DD19] is that partite one-sided HDX also give rise to
tuple-splitting trees.

######  Example 10.6.

Let $\lambda\geqslant 0$ and let $X$ be a $d$-uniform two-sided $\lambda$-high
dimensional expander. Then for any binary tree $T$ and labeling $\rho$ that
satisfy the first and second item in Definition 10.4, $(X,T,\rho)$ is a
$d^{2}\lambda$-tuple splitting tree.

Finally, [Ale+20, Corollary 9.18] also prove that walks on expander graphs are
splittable. Let us define the complex formally. Let $G=(V,E)$ be a graph and
$k\in\mathbb{N}$. Let $W_{G}$ be the following $k$-partite simplicial complex

$\SC[W][1][G]=V\times[k],$
$\SC[W][k][G]=\left\\{\\{(v_{1},1),(v_{2},2),\ldots,(v_{k},k)\\}\left|\;\vphantom{\\{(v_{1},1),(v_{2},2),\ldots,(v_{k},k)\\}(v_{1},v_{2},\ldots,v_{k})\text{
is a walk in }G}\right.(v_{1},v_{2},\ldots,v_{k})\text{ is a walk in
}G\right\\}.$

We choose a face in $\SC[W][k][G]$ by choosing a vertex $v_{1}\in V$ according
to the stationary distribution over vertices in $G$ and then taking a
$(k-1)$-length random walk on that vertex.

######  Example 10.7.

Let $G$ be a $\lambda$-expander and $T,\rho$ an ordered partite tree. If every
$u\in\mathcal{I}$ satisfies:

$\max\rho(\ell_{u})<\min\rho(r_{u}),$

then $(W_{G},T,\rho)$ is a $\lambda$-splittable tree.

####  10.1.2 Operations on splitting trees

We will need several further operations on splitting trees for our analysis: a
pruning method that allow us to analyze higher dimensionalT faces, and a
partitification technique that allows us to reduce standard splitting trees to
the tuple setting.

We start with the latter. Recall $X$’s partitification is the complex

$\SC[P][k]\coloneqq\left\\{(s,\pi)\coloneqq\left\\{(s_{\pi(1)},1),(s_{\pi(2)},2),\ldots,(s_{\pi(k)},k)\right\\}\left|\;\vphantom{(s,\pi)\coloneqq\left\\{(s_{\pi(1)},1),(s_{\pi(2)},2),\ldots,(s_{\pi(k)},k)\right\\}s\in\X[k],\pi\in
S_{k}}\right.s\in\X[k],\pi\in S_{k}\right\\},$

This notion extends naturally to splitting trees.

######  Definition 10.8.

Let $(X,T,\rho)$ be a $d$-uniform $\lambda$-splitting tree, and
$\rho^{\prime}:T\to[d]$ a well-ordered labeling such that
$|\rho^{\prime}(u)|=\rho(u)$ for every $u\in T$. The _$\rho^{\prime}$
-partitification_ of $(X,T,\rho)$ is defined to be the tuple splitting tree
$(P,T,\rho^{\prime})$.

Any un-ordered splitting tree can be embed into a tuple splitting tree by
taking any partitification.

######  Claim 10.9.

Let $(X,T,\rho)$ be a $\lambda$-splitting tree. Every
$\rho^{\prime}$-partitification of $(X,T,\rho)$ is a $\lambda$-tuple splitting
tree.

###### Proof.

It suffices to show for every internal node $u\in\mathcal{I}$ with
$\rho^{\prime}(\ell(u))=A$ and $\rho^{\prime}(r(u))=B$ that $S_{A,B}(P)$ is a
$\lambda$-bipartite expander. This follows from the observation that
$S_{A,B}(P)$ is isomorphic to the bipartite graph with left vertices
$L=\X[|A|]\times[|A|!]$, right vertices $R=\X[|B|]\times[|B|!]$, and edges
$(s,i)\to(t,j)$ for all $i\in A,j\in B$, and $(s,t)$ such that $s\sim t$ in
$S_{\rho(\ell_{u}),\rho(r_{u})}$.191919Formally, the edge $(s,i)\to(t,j)$ also
inherits the weight $\frac{\operatorname*{\mathbb{P}}(st)}{|A||B|}$ from
$S_{\rho(\ell_{u}),\rho(r_{u})}$. It is a standard fact that such a bipartite
construction inherits its expansion from $S_{\rho(\ell_{u}),\rho(r_{u})}$, and
is therefore a $\lambda$-bipartite expander. ∎

Finally, we note that tuple splitting trees can be pruned to create new
splitting trees. Let $(X,T,\rho)$ be a tuple splitting tree with $k$ leaves.
Let $u\in\mathcal{I}$ be an internal node whose label is $F=\rho(u)$. Let
$P=P(X,F)$ be the partite complex with vertices $\SC[P][1]=\SC[X^{[k]\setminus
F}][1]\mathbin{\mathaccent 0{\cdot}\cup}X[F]$ and top level faces
$t\mathbin{\mathaccent 0{\cdot}\cup}\\{s\\}$ such that $t\mathbin{\mathaccent
0{\cdot}\cup}s\in\X[k]$, inheriting the corresponding densities. In other
words, we replace the vertices of $X$ in $\SC[X^{F}][1]$ with the set of faces
$X[F]$.

Let $T(u)$ be the sub-tree of $T$ rooted by $u$. Let $T^{\prime}=(T\setminus
T(u))\cup\\{u\\}$. Let $\rho^{\prime}:T^{\prime}\to([k]\setminus
F)\cup\\{F\\}$ be the labeling that replaces the subset $F$ with a single
replacement index $f$:

$\rho^{\prime}(v)=\begin{cases}(\rho(v)\setminus
F)\cup\\{f\\}&F\subseteq\rho(v)\\\ \rho(v)&otherwise\end{cases}.$

######  Definition 10.10 (Pruning Trees).

Let $(X,T,\rho)$ be a $\lambda$-tuple splitting tree with $k$ leaves. Let
$u\in T$ be a non-leaf node whose label is $F=\rho(u)$. The $u$-pruning of the
tree is the triple $(P(X,F),T^{\prime},\rho^{\prime})$.

######  Claim 10.11.

Let $(X,T,\rho)$ be a $\lambda$-tuple splitting tree. Let $u\in T$ be a non-
leaf node. Then the $u$-pruning is also a $\lambda$-splitting tree. ∎

The proof follows directly from the definitions and we therefore omit it.

Finally, it will be convenient to introduce notation for sequential pruning,
that is given a collection of disjoint color sets
$\mathcal{F}=\\{F_{1},\ldots,F_{m}\\}$, we denote the sequential pruning of
$X$ by $\mathcal{F}$ as $P(X,\mathcal{F})\coloneqq
P(...P(X,F_{1}),F_{2}),F_{m})$. Note that the resulting complex is independent
of the order of $\mathcal{F}$, so $P(X,\mathcal{F})$ is well-defined. One can
similarly define a sequentially pruned splitting tree as above. It is
immediate from Claim 10.11 that these are also $\lambda$-tuple splitting.

####  10.1.3 Hitting set and Bias amplification

In this section, we prove two basic ‘sampling-type’ properties for splitting
trees: hitting set and bias amplification. We start with the former. Recall a
complex is $(\gamma,i)$-hitting if for any $A\subset\X[0]$:

$\operatorname*{\mathbb{P}}_{\sigma\in\X[i]}[\sigma\subset
A]\leqslant\mu(A)^{i}+\gamma$

######  Proposition 10.12 (Hitting Set).

Any depth $D$ $\lambda$-(tuple) splitting tree with $k$ leaves is
$(3^{D}\lambda,k)$-hitting.

Splitting trees also exhibit strong bias amplification, used to build balanced
error correcting codes.

######  Proposition 10.13 (Bias-Amplification).

Let $(X,T,\rho)$ be a $\lambda$-tuple splitting tree for
$\lambda<\frac{1}{16}$. For any $0<\varepsilon<\frac{1}{4}$ and family of mean
$\varepsilon$ functions $\\{f_{i}:X[i]\to\\{\pm 1\\}\\}_{i\in[k]}$, $\prod
f_{i}$ is a $\\{\pm 1\\}$-valued function with bias at most:

$\left\lvert\operatorname*{\mathbb{E}}_{{a\in{\X[k]}}}\left[\prod_{i=1}^{k}f_{i}(a_{i})\right]\right\rvert\leqslant\varepsilon^{k}+2\lambda$
(10.1)

While Proposition 10.12 and Proposition 10.13 are elementary, to the authors’
knowledge they do not appear in the literature. Prior works on HDX (e.g.
[DK17, Ale+20]) use weaker variants of these lemmas which require super-
exponential overhead to achieve a given distance or bias, while the above only
requires quasi-polynomial overhead. We discuss this in greater detail in
Section 10.

These results are immediate corollaries of a functional variant of [DD19]’s
“high dimensional expander-mixing lemma” (HD-EML) extended to splitting trees.
We give the statement here and include a proof in the appendix for
completeness along with the proofs of Proposition 10.12 and Proposition 10.13.

######  Theorem 10.14 (high dimensional expander Mixing Lemma).

Let $(X,T,\rho)$ be a depth $D$ $\lambda$-tuple splitting tree with $k$
leaves. Denote by $d_{i}$ the depth of the leaf labeled $i$. Then for any
family of functions $\\{f_{i}:X[i]\to\mathbb{R}\\}_{i\in[k]}$:

$\left\lvert\operatorname*{\mathbb{E}}_{{a\in{\X[k]}}}\left[\prod_{i=1}^{k}f_{i}(a_{i})\right]-\prod_{i=1}^{k}\operatorname*{\mathbb{E}}_{{a_{i}\in
X[i]}}\left[f_{i}(a_{i})\right]\right\rvert\leqslant
3^{D}\lambda\prod_{i=1}^{k}\lVert f_{i}\rVert_{2^{d_{i}}}.$ (10.2)

If $(X,T,\rho)$ is instead a depth $D$ standard $\lambda$-splitting tree, we
take $\\{f_{i}:\X[1]\to\mathbb{R}\\}_{i\in[k]}$ and have:

$\left\lvert\operatorname*{\mathbb{E}}_{{a\in{\X[k]},\pi\in
S_{k}}}\left[\prod_{i=1}^{k}f_{i}(a_{\pi(i)})\right]-\prod_{i=1}^{k}\operatorname*{\mathbb{E}}_{{a_{i}\in{\X[1]}}}\left[f_{i}(a_{i})\right]\right\rvert\leqslant
3^{D}\lambda\prod_{i=1}^{k}\lVert f_{i}\rVert_{2^{d_{i}}}.$ (10.3)

In the future, we state our results only for the partite setting unless there
is a substantial difference in proof or parameters for the results. Otherwise,
we collect analog statements for the unordered case at the end of Appendix D
for completeness.

We close the subsection with a few remarks. First it should be noted that for
the special case of expander walks, better hitting set and bias amplification
methods are known (indeed one can achieve polynomial overhead vs our
quasipolynomial bound above). Nevertheless, it is useful to have these lemmas
on structures like HDX that admit stronger properties like agreement tests. We
remark it is also actually possible to use the high dimensional expander
mixing lemma for splitting trees directly to prove a different variant of
Chernoff-Hoeffding by reduction to the complete complex. However, this results
in exponentially worse parameters than our arguments in Section 5, and we will
not need the result in the following.

###  10.2 Coding Preliminaries

A $q$-ary error correcting code $C$ over a finite size-$q$ alphabet $\Sigma$
is a subset $C\subset\Sigma^{n}$, where $n\in\mathbb{N}$ is called the block
length. We say a code is linear if $\Sigma=\mathbb{F}_{p}$ for prime power $p$
and $C$ is a subspace, and $\mathbb{F}_{p}$-linear if
$\Sigma=\mathbb{F}_{p}^{k}$ for some $k\in\mathbb{N}$ and $C$ is a subspace of
$(\mathbb{F}_{p}^{k})^{n}$.

The rate of a code $C$, which measures its overhead, is
$r=\frac{\log_{|\Sigma|}(|C|)}{n}$, and its distance, which captures the codes
error correction capability, is the minimum normalized hamming distance
between any two codewords

$d\coloneqq\min_{c_{1},c_{2}\in C}\left\\{\frac{|\\{i\in[n]:c_{1}(i)\neq
c_{2}(i)\\}|}{n}\right\\}.$

We remark that for any $\mathbb{F}_{p}$-linear code, the distance is the
minimum weight of a non-zero codeword. For ease of notation, we will call a
$q$-ary code with rate $r$ and distance $d$ an $(r,d)_{q}$-code.

We will be interested in so-called “good” families of codes, which are
infinite families with growing block length and constant rate and distance. We
will focus in particular in this section on building large distance
$\mathbb{F}_{2}$-linear codes over $\Sigma=\mathbb{F}_{2}^{k}$. In this regime
there is a classical upper bound due to McEliece, Rodemich, Rumsey, and Welch
[McE+77] stating that good $q$-ary codes have distance at most
$1-\frac{1}{q}$, or more exactly:

######  Theorem 10.15 (MRRW Bound [McE+77]).

For all $\varepsilon>0$ and $q\in\mathbb{N}$, any family of $q$-ary codes with
distance $1-\frac{1}{q}-\varepsilon$ has rate at most:

$r\leqslant O\left(\varepsilon^{2}\log(1/\varepsilon)\right).$

Given a code $C$, a unique decoding algorithm with radius $\gamma\in[0,1/2]$
is a (possibly randomized) algorithm $Dec:\Sigma^{n}\to C$ which given any
$w\in\Sigma^{n}$ such that $dist(w,C)\leqslant\gamma$ outputs the uniquely
closest $y\in C$ to $w$. Note that unique decoding is only possible up to
radius $\lfloor\frac{nd-1}{2n}\rfloor\leqslant 1/2$, even with large alphabet,
as there may be no unique closest codeword beyond this point.

List-decoding is the natural extension of unique decoding beyond the
$\frac{1}{2}$ barrier. A code is said to be list-decodable with radius $t$ if
there is an algorithm which outputs a list of all codewords within radius $t$
of the given word. We first give the combinatorial definition, which simply
bounds the number of codewords around any fixed point.

######  Definition 10.16 (Combinatorial List-decoding).

For $\gamma\in(0,1)$ and $L\in\mathbb{N}$, a code $C$ is said to be
$(\gamma,L)$ list-decodable if for every $z\in Y$, there are at most $L$
codewords $x\in C$ such that $dist(x,z)<\gamma$.

In this section, we will be interested in efficient algorithms for list-
decoding, typically a much more challening task than the existential
definition.

######  Definition 10.17 (Efficient List-decoding).

For $\delta>0$, $\gamma\in(0,1)$ and $L\in\mathbb{N}$, a family of codes
$\\{C_{n}\\}$ is said to be efficiently $(\gamma,L)$ list-decodable with
confidence $\delta$ if it is combinatorially $(\gamma,L)$ list-decodable and
there exists a (randomized) polynomial time202020Here we mean polynomial in
the block length. algorithm Dec$:\Sigma^{n}\to P(C)$ such that for every word
$w\in\Sigma^{n}$:

$\textsc{Dec}(w)=\\{c\in C:\text{dist}(c,w)<\gamma\\}$

except with probability $\delta$.

Another classical approach to handling the high error regime is local
testability. A code $C$ is said to be locally testable if there is a
(randomized, non-adaptive) algorithm $\mathcal{T}_{C}$ which on input of a
word $w\in\Sigma^{n}$, queries constantly many symbols of $w$ and rejects with
high probability if it is far from the code. In practice, if one receives such
a word, instead of trying to list decode they could simply request re-
transmission. More formally, we consider the following standard notion of
‘strong’ local testability:

######  Definition 10.18 (Locally Testable Code).

For any $s>0$ and $q\in\mathbb{N}$, a code $C$ of blocklength $n$ is said to
be $(q,s)$-locally testable if there exists a function
$\mathcal{T}_{C}:[n]^{q}\times\Sigma^{q}\to\\{0,1\\}$ and a distribution
$\mathcal{D}$ over $[n]^{q}$ such that on any word $w\in\Sigma^{n}$, the pair
$(\mathcal{T}_{C},\mathcal{D})$ (called the tester) satisfies:

  1. 1.

Completeness: If $w\in C$, then
$\operatorname*{\mathbb{P}}_{J\sim\mathcal{D}}[\mathcal{T}_{C}(J,w_{J})=1]=1$

  2. 2.

Soundness:
$\operatorname*{\mathbb{P}}_{J\sim\mathcal{D}}[\mathcal{T}_{C}(J,w_{J})=0]\geqslant
s\cdot\text{dist}(w,C)$

We call $q$ the locality, and $s$ the soundness.

Typically we will simply think of $\mathcal{T}_{C}$ as a randomized algorithm
and write $\mathcal{T}_{C}(w)$ to denote its application on the word $w$,
dropping the distribution of the tester when clear from context. We will work
with testers that have one additional constraint: their queries should be
marginally uniform.

######  Definition 10.19 (Uniform LTC).

$(\mathcal{T},\mathcal{D})$ is called uniform if every marginal of
$\mathcal{D}$ is uniform over $[n]$.

We remark that focusing on uniform LTCs is not particularly restrictive—since
codes do not typically have ‘preferred’ coordinates, most natural
constructions are uniform.

Finally, though not strictly necessary, we will assume throughout that all
complexes in this section are “homogenous” subsets $X\subset[n]^{k}$, meaning
that their marginal distribution over each part is uniform over $[n]$. We
remark that in the context of high dimensional expanders, any partite ‘type-
regular’ complex can be homogenized in this fashion while maintaining
expansion and bounded degree (see [FI20] for details). As most known
constructions of HDX are type-regular, this is not a particularly restrictive
assumption, and it is also known to hold for other classical splitting trees
such as expander walks [Ale+20].

###  10.3 The ABNNR Construction

In the previous section, we proved several ‘agreement theorems’ on simplicial
complexes. These well-studied tests are actually very closely related to both
local testability and list decoding of a particular family of codes called
direct product codes, corresponding exactly to the set of ‘global functions’
discussed in Section 8. At a broader level, these are themselves a special
case of a well-studied family of codes introduced in the seminal work Alon,
Bruck, Naor, Naor and Roth [Alo+92] called the ‘ABNNR’-construction. We focus
on the case of $\mathbb{F}_{2}$ for simplicity, though our results extend
naturally to larger fields.

######  Definition 10.20 (the ABNNR Construction).

Given a right $k$-regular bipartite graph $G=(L,R,E)$ and a base code
$C\subseteq\mathbb{F}_{2}^{L}$, the “ABNNR-Encoding” of $C$ with respect to
$G$ is the code $\text{Im}(E_{G}(C))$ where $E_{G}$ is an “encoding” map
$E_{G}:\mathbb{F}_{2}^{|L|}\to(\mathbb{F}_{2}^{k})^{|R|}$ defined by setting
for each $c\in C$ and $v\in R$:

$E_{G}(c)_{v}=c|_{N(v)}.$

In other words, each right vertex concatenates the symbols of its neighbors to
create a new code over $R$. One can check that in Section 8, the set of global
functions is exactly the ABNNR encoding over the inclusion graph
$(\X[j],\X[k])$. For a general $k$-uniform complex $X$ and $j\leqslant
i\leqslant k$, we write $E^{(j,i)}_{X}$ to mean the ABNNR-encoding on the
vertex inclusion graph $(\X[i],\X[j])$. In the special case where $i=k$ and
$j=1$, we write just $E_{X}$ to denote the ABNNR-encoding over the inclusion
graph $([n],\X[k])$, where inclusion is viewed taking $\X[k]\subseteq[n]^{k}$
as ‘ordered tuples’ of $[n]$, rather than as faces of a simplicial complex.
This is a minor difference, but is a bit more convenient in the setting of
amplifying base codes.

Recent years have seen a great deal of work on instantiating the ABNNR
construction on high dimensional expanders and splitting trees [DK17, Din+18,
Ale+20, JST21, BD22, JST23], in particular in the context of efficient list-
decoding. Building on tools from these works, we give the first family of
large alphabet codes with near-optimal distance that are simultaneously
locally testable and list-decodable.

######  Theorem 10.21.

For all large enough $k\in\mathbb{N}$ and all $\varepsilon>0$, there exists an
explicit family of $\mathbb{F}_{2}$-linear ABNNR-Codes that are
simultaneously:

  1. 1.

$(\varepsilon^{O(k)},1-2^{-k}-\varepsilon)_{2^{k}}$-codes

  2. 2.

$(O(1),\frac{O(1)}{k\log(1/\varepsilon)})$-locally testable.

  3. 3.

$(1-2^{-\Omega(k)},2^{O(k)})$-efficiently list-decodable with confidence
$2^{-\Omega(n-k)}$ whenever $\varepsilon\leqslant 2^{-\Omega(k)}$.

We remark that very recently, Jeronimo, Srivastava, and Tulsiani [JST23] gave
a direct list-decoding algorithm for the LTCs of [Din+22] (which have some
small constant distance $d\ll\frac{1}{2}$). To our knowledge, these are the
only other examples of codes that are simultaneously $c^{3}$-LTC and
efficiently list-decodable.

The remainder if this section is split into three parts focused respectively
on distance amplification, local-testability, and list-decoding of the ABNNR
construction, and a short fourth section devoted to a conjectural approach to
removing the soundness decay in Theorem 10.21. Each section is independent,
containing both the corresponding component of Theorem 10.21 as well as more
general results within the framework. To facilitate this structure we first
give a brief proof overview of Theorem 10.21 that doubles as a roadmap for the
section.

##### Proof Overview

The high level idea behind Theorem 10.21 is simple: starting with a binary
locally testable ‘base code’ $C$ with distance near $\frac{1}{2}$, we will
argue that the ABNNR-encoding of $C$ on any $k$-partite splitting
tree212121Formally for list-decoding actually require a slightly stronger
notion called ‘complete’ splittability, c.f. Definition 10.31. has distance
near $1-2^{-k}$ (Corollary 10.24), is list-decodable (Theorem 10.32), and
maintains local testability (Theorem 10.25). Instantiating this framework on
expander walks (the sparsest known family of splitting trees) gives codes with
the claimed parameters. We give a brief description of each step.

Distance amplification on splitting trees is fairly elementary, and follows
from the hitting-set lemma. This is a standard argument: one observes that the
two encoded symbols $E(x),E(x^{\prime})$ differ in any face which hits the
vertex set $1_{x\neq x^{\prime}}$. Since by assumption the base code has
distance roughly $1/2$, the hitting set lemma promises this set is hit except
with roughly $2^{-d}$ probability (see Corollary 10.24). Theorem 10.21
actually uses a slightly stronger distance amplification lemma for expander-
walks and is given in Corollary 10.30. The weaker amplification lemma (in
particular its bias variant) appears later in the proof as a sub-component of
the list-decoding algorithm.

List-Decoding the ABNNR construction, despite being heavily studied on HDX and
splitting trees, is surprisingly tricky. Roughly speaking there are two main
issues. First, known list-decoding algorithms for this setting are actually
either for an $\mathbb{F}_{2}$-valued variant of ABNNR called the direct sum
construction [Ale+20, JST21, BD22], or only hold on two-sided HDX [Ale+20,
Din+18] (which have exponentially worse rate). To handle this, we build a
reduction from list-decoding the ABNNR-encoding on $X$ to list-decoding the
direct sum encodings of its projected sub-complexes $X^{F}$. The second issue
with this strategy is that known list-decoding algorithms for direct sum
[JST21, BD22] actually requires the base code to be $\varepsilon$-biased, a
stronger condition than simply having distance near $\frac{1}{2}$. We will
discuss how to construct such base codes shortly. We instantiate this
framework in Corollary 10.35 to prove the list-decoding component of Theorem
10.21.

Local Testability of the ABNNR construction, to our knowledge, has not been
studied outside the special case of agreement testing. Our test follows a very
simple strategy. We first check whether the given word $f$ is a direct product
(in the sense of Section 8) via a simple 2-query agreement test: pick a random
vertex $v\in[n]$, and independently $s,s^{\prime}\supset v$, and check whether
$f_{s}$ and $f_{s^{\prime}}$ match on $v$. If this test passes, we then
simulate the tester on the ‘direct product decoding’ of $f$. That is, for
every location the base tester queries, we pick a random face including that
vertex and feed the tester its value in the word $f$. We prove this procedure
is sound in Theorem 10.25, and instantiate the process in Corollary 10.30 to
prove the local testability component of Theorem 10.21.

The Base Code for our construction, as discussed above, must be an
$\varepsilon$-biased $c^{3}$-LTC. $c^{3}$-LTCs with distance near
$\frac{1}{2}$ are now known due to the breakthrough works of [Din+22, PK22]
combined with LTC distance-amplification techniques of [Kop+17], but the
latter amplification causes several core issues that make the tecnique largely
useless for our setting: 1) the resulting codes make
$\operatorname{poly}(1/\varepsilon)$ queries, 2) may not be
$\varepsilon$-biased, and 3) are heavily randomized. We remedy these issues
via the ABNNR-construction itself. In particular, starting with the base LTC
of [Din+22], we encode it into $\log(1/\varepsilon)$-uniform walks on an
expander graph using ABNNR, and then concatenate with the Hadamard code. This
code is $\varepsilon$-biased roughly because concatenating with the perfectly
balanced Hadamard code converts the good distance of the ABNNR-encoding into
good bias, and the resulting code is locally testable using the Hadamard’s
classical local decoding and local testing algorithms. We formalize this step
in Proposition 10.29

Finally we summarize the construction and proof below:

Code underlying Theorem 10.21: 1. Start with the base $c^{3}$-LTC $C$ of
[Din+22] 2. Amplify $C$’s distance via expander walks 3. Reduce alphabet and
bias by concatenating with Hadamard 4. Re-amplify the resulting code via a
second set of expander walks.

###### Proof of Theorem 10.21.

Bias, rate, and local-testability are proven in Corollary 10.30. List-
decodability is proved in Corollary 10.35. ∎

###  10.4 Distance Amplification

The ABNNR construction is one of the most classical distance amplification
methods in coding theory. The standard result to this effect is that
instantiating the framework on a (bounded degree) additive sampler amplifies
distance while maintaining rate up to a constant factor.

######  Lemma 10.22 ([Alo+92]).

Let $G=(L,R,E)$ be a right $k$-regular bipartite graph such that $(R,L,E)$ is
an $(\alpha,\beta)$-sampler. If $C\subset\mathbb{F}_{2}^{|L|}$ is a code of
distance $\alpha$ and rate $r$, then $E_{G}(C)$ is a
$(r\frac{|L|}{|R|},1-\beta)_{2^{k}}$-code.

This observation was used in [DK17, Din+18] to give distance amplification for
codes defined on HDX. Our sampling lemmas imply an exponential improvement in
the rate-distance trade-off of such codes. We choose a fairly arbitrary
setting of our parameters for simplicity, but any setup with good sampling
works:

######  Corollary 10.23 (Distance Amplification on HDX).

For any $\alpha,r,c>0$, let $C$ be a base code of distance $\alpha$ and rate
$r$. Let $X$ be a $d$-uniform $c$-nice complex. Then for any $i<j\leqslant d$
and $G=(\X[i],\X[j])$ the ABNNR code $E^{i,j}_{X}(C)$ is an
$(r^{\prime},d^{\prime})_{|\Sigma|}$-code for

$r^{\prime}=r\frac{|\X[i]|}{|\X[j]|},\quad\quad
d^{\prime}=1-\frac{1}{\alpha}\exp\left(\Omega_{c}\left(\alpha^{2}\frac{j}{i}\right)\right),\quad\quad|\Sigma|=2^{\binom{j}{i}}.$

Note that when $i=1$, Corollary 10.23 has alphabet size $|\Sigma|=2^{j}$ and
distance $1-\operatorname{poly}(|\Sigma|^{-1})$, optimal up to polynomial
factors by Theorem 10.15. However, in this special case, it is actually
possible achieve optimal amplification directly via the hitting set lemma
(Proposition 10.12).

######  Corollary 10.24 (Distance Amplification for Splitting Trees).

For any $\alpha,r>0$, let $C$ be a base code of distance $\alpha$ and rate
$r$. If $X$ is a $k$-uniform $\lambda$-(tuple)-splitting tree of depth $D$,
then $E_{X}(C)$ is an $(r^{\prime},d^{\prime})_{|\Sigma|}$-code for

$r^{\prime}=r\frac{n}{|\X[k]|},\quad\quad
d^{\prime}=1-(1-\alpha)^{k}-3^{D}\lambda,\quad\quad|\Sigma|=2^{k}$

Moreover when $\alpha=\frac{1}{2}(1-\varepsilon)$, then $d^{\prime}\geqslant
1-\frac{1}{2^{k}}(1+\varepsilon)^{k}-3^{D}\lambda$.

###### Proof.

Rate and alphabet size are immediate from construction. Let $x,x^{\prime}\in
C$ be any two distinct non-zero codewords. We wish to bound the distance
between their encodings $E_{X}(x)$ and $E_{X}(x^{\prime})$, which is exactly
the hitting probability of $1_{x\neq x^{\prime}}$ in the inclusion graph
$([n],\X[k])$. By the distance of $C$ we are promised that
$\mu(1_{x=x^{\prime}})\leqslant 1-\alpha$, so Proposition 10.12 gives the
desired result.222222Proposition 10.12 is formally for $(\X[1],\X[k])$, but
because $X$ is homogenous the bound carries over by simply setting each
partite component of $A$ to be $A_{i}=1_{x=x^{\prime}}$. Plugging
$\alpha=\frac{1}{2}(1-\varepsilon)$ into the resulting bound gives the final
line. ∎

###  10.5 Local Testability of ABNNR

In this section, we prove the ABNNR encoding of a locally testable code is
locally testable.

######  Theorem 10.25 (Local Testability of ABNNR).

For any uniform $(q,s)$-LTC of blocklength $n$ and $(k_{L},k_{R})$-regular
bipartite graph $G=(L,R,E)$ on $|L|=n$ vertices, $E_{G}(C)$ has a uniform
$(q+2,\frac{cs}{qk_{R}})$-local tester.

Our proof relies on the following elementary agreement test. Given a word $f$,
denote by $\mathcal{T}_{G}(f)$ the following process:

  1. 1.

Pick a uniformly random vertex $v\in L$

  2. 2.

Pick two uniformly random neighbors $w,w^{\prime}\in N(v)$

  3. 3.

Accept if and only if $f_{w}(v)=f_{w^{\prime}}(v)$

In the agreement notation of the previous section, we’d write the word $f$ as
an ensemble $\mathcal{F}=\\{f_{w}:N(w)\to\mathbb{F}_{2}\\}_{w\in R}$ and
denote the acceptance probability of this test as $Agree_{0}(\mathcal{F})$. We
will move between these two viewpoints interchangeably. $\mathcal{T}_{G}$ is
clearly complete. Its soundness follows from a general result of [GC19]:

######  Lemma 10.26 ([GC19, Lemma 5.2]).

There exists a universal constant $c\geqslant 1$ such that for all
$\varepsilon>0$ and any ensemble $\mathcal{F}$:

$Agree_{0}(\mathcal{F})\geqslant 1-\varepsilon\quad\implies\quad
dist(F,g_{\text{maj}})\leqslant ck_{R}\varepsilon$

where for $v\in L$ we define $g_{\text{maj}}(v)\coloneqq\text{plurality}_{w\in
N(v)}\\{f_{w}(v)\\}$.232323Ties can be broken arbitrarily.

With this in mind, we prove Theorem 10.25 via the following natural tester:
given a word $f\in(\mathbb{F}_{2}^{k_{R}})^{R}$, run the DP-tester on $w$, and
the base code tester on the plurality decoding of $f$ if it passes:

  1. 1.

Run $\mathcal{T}_{G}$ on $f$

  2. 2.

For every $v\in L$ that $\mathcal{T}_{C}$ would query:

     * –

Sample a random neighbor of $v$: $w\sim N(v)$

     * –

Denote the ‘decoded’ plurality as $g_{\text{dec}}(v)=f_{w}(v)$

  3. 3.

Run $\mathcal{T}_{C}$ on $g_{\text{dec}}$

###### Proof of Theorem 10.25.

Query complexity and completeness are immediate from construction. The tester
is uniform since the base code is uniform, and picking a uniformly random
vertex $v\in L$ and random $w\in N(v)$ is uniformly distributed over $R$.

Toward analyzing soundness, fix any $\delta\in[0,1]$ and $f$ some word at
distance $dist(f,E_{X}(C))=\delta$. We need to show the test rejects on $f$
with probability at least $\delta c^{\prime}\frac{s}{qk_{R}}$ for some
$c^{\prime}\geqslant 0$. Observe that we may assume $\mathcal{T}_{G}(f)$
passes with probability at least $1-\delta\frac{1}{4c}\frac{s}{qk_{R}}$, since
otherwise Step (1) rejects with probability at least
$\delta\frac{1}{4c}\frac{s}{qk_{R}}$ and we are done. We claim that
conditioned on this event, the following two properties hold:

  1. 1.

$g_{\text{dec}}$ matches $g_{\text{maj}}$ with high probability:

$\operatorname*{\mathbb{P}}_{S\sim\mathcal{T}_{C}}[\exists v\in
S:g_{\text{dec}}(v)\neq g_{\text{maj}}(v)]\leqslant\frac{s}{4ck_{R}}\delta$

  2. 2.

$g_{\text{maj}}$ is far from the base code:

$dist(g_{\text{maj}},C)\geqslant\frac{1}{2k_{R}}\delta.$

Soundness is then immediate: as long as the base tester $\mathcal{T}_{C}$
receives the ‘correct’ symbols from $g_{\text{maj}}$, it rejects with
probability $s\cdot dist(g_{\text{maj}})\geqslant\frac{s}{2k_{R}}\delta$ by
Item 2. Since the former occurs with probability at least
$\frac{s}{4k_{R}}\delta$ by Item 1, the total rejection probability is at
least $\frac{s}{2k_{R}}\delta-\frac{s}{4k_{R}}\delta=\frac{s}{4k_{R}}\delta$
as desired.

It is left to prove the claimed properties.

##### Proof of Item 1

Observe that since the queries are marginally uniform, by a union bound it is
enough to show that the decoding of a uniformly random vertex succeeds except
with probability $\frac{s}{4cqk_{R}}\delta$. The proof is essentially a
simpler variant of Claim 8.2. For a fixed $v\in L$ define the set of ‘bad’
neighbors as those whose labeling disagrees with the plurality decoding as:

$B_{v}\coloneqq\\{w\in N(v):f_{w}(v)\neq g_{\text{maj}}(v)\\}.$

The failure probability of our single-query decoding procedure is exactly
$\underset{v\in L}{\mathbb{E}}[B_{v}]$, so it is enough to show

$\mathbb{E}[B_{v}]\leqslant\frac{s}{4cqk_{R}}\delta.$

This follows from the fact that the test $\mathcal{T}_{G}$ can be written as
an expectation over complete local distributions. In particular, observe that
we can decompose $\mathcal{T}_{G}$ as:

$Agree_{0}(f)=\operatorname*{\mathbb{P}}_{v\sim L,w,w^{\prime}\sim
N(v)}[f_{w}(v)=f_{w^{\prime}}(v)]\geqslant 1-\frac{s}{4cqk_{R}}\delta.$

This implies that the expected probability that $f_{w}(v)\neq
f_{w^{\prime}}(v)$ in the local distribution is at most:

$\underset{v\sim
L}{\mathbb{E}}\left[\operatorname*{\mathbb{P}}_{w,w^{\prime}\sim
N(v)}[f_{w}(v)\neq
f_{w^{\prime}}(v)]\right]\leqslant\frac{s}{4cqk_{R}}\delta.$

Since $w$ and $w^{\prime}$ are independent neighbors of $v$, the inner term is
at least

$\operatorname*{\mathbb{P}}_{w,w^{\prime}\sim N(v)}[f_{w}(v)\neq
f_{w^{\prime}}(v)]=2\mathbb{E}[B_{x}]\mathbb{E}[\overline{B_{v}}]\geqslant\mathbb{E}[B_{v}]$

since $\mathbb{E}[\overline{B_{v}}]\geqslant\frac{1}{2}$ by construction,
which completes the proof.

##### Proof of Item 2

The proof follows from the fact that conditioned on Step (1) (the agreement
test) passing, $E_{X}(g_{\text{maj}})$ is close to a DP-codeword. Thus if
$g_{\text{maj}}$ itself is too close to $C$, it’s encoding will be close to
$E_{G}(C)$ violating our original assumption on the distance. Formally, assume
for the sake of contradiction that $g_{\text{maj}}$ is not
$\frac{\delta}{2k_{R}}$-far from $C$. Then there exists $x\in C$ such that
$dist(g_{\text{maj}},x)<\frac{\delta}{2k_{R}}$. Since $G$ is bi-regular, this
further implies a bound on the distance of the encodings of $g_{\text{maj}}$
and $x$:

$\displaystyle dist(E^{k}_{G}(g_{\text{maj}}),E_{G}^{k}(x))$
$\displaystyle=\operatorname*{\mathbb{P}}_{w\sim
R}[E_{G}(g_{\text{maj}})(w)\neq E_{G}(x)(w)]$ $\displaystyle\leqslant
k_{R}\operatorname*{\mathbb{P}}_{w\sim R,v\sim
N(w)}[E_{G}(g_{\text{maj}})(w)_{v}\neq E_{G}(x)(w)_{v}]$
$\displaystyle=k_{R}dist(g_{\text{maj}},x)$ $\displaystyle<\frac{\delta}{2}.$

where the second equality follows from the fact that since $G$ is bi-regular,
sampling a uniformly random vertex $v\in R$ and a random $s\in N(v)$ is
equidistributed with sampling a random $w\in L$. Finally closeness of the
encoded words contradicts the fact that $f$ is $\delta$-far from $E_{G}(C)$,
since $E_{G}(x)$ is a codeword and by the triangle inequality:

$dist(f,E_{G}(x))\leqslant
dist(f,E_{G}(g_{\text{maj}}))+dist(E_{G}(g_{\text{maj}}),E_{G}(x))<\delta,$

where we have used the fact that since $Agree_{0}(f)\geqslant
1-\frac{s}{4cqk_{R}}$ by assumption, $f$ is $\frac{s}{4q}\delta$-close to
$E_{G}(g_{\text{maj}})$ by Lemma 10.26. ∎ We remark that it is likely possible
to reduce the query complexity of the above argument to just $q+1$ by re-using
the first query of $\mathcal{T}_{C}$ for the agreement test and performing a
more careful conditioned analysis on the latter passing. Since $q$ for us is
some small constant, the difference between $q+1$ and $q+2$ is negligible so
we only give the simpler independent version above.

To prove Theorem 10.21, we need a good explicit family of binary linear LTCs
with near optimal distance to amplify via Theorem 10.25. In fact, as discussed
in the proof overview we will need base codes with the stronger property of
having small bias:

$bias(C)\coloneqq\max_{c\in
C\setminus\\{0\\}}\left\\{\left|\mathbb{E}_{i\in[n]}[(-1)^{c_{i}}]\right|\right\\}.$

Note that an $\varepsilon$-biased linear code always has distance at least
$\frac{1-\varepsilon}{2}$ since for every $c\in C$,
$\left\lvert\operatorname*{\mathbb{E}}_{{i\in{[n]}}}\left[(-1)^{c_{i}}\right]\right\rvert=1-2\operatorname{dist}(c,0)$.
Our base codes start with the breakthrough construction of $c^{3}$-LTCs by
Dinur, Evra, Livne, Lubotzky, and Moses [Din+22]:

######  Theorem 10.27 ([Din+22]).

There exists an explicit infinite family of binary, linear, uniform LTCs with
constant rate, distance, locality, and soundness, and a linear time unique
decoder up to constant radius.

We remark that while [Din+22] do not argue their testers are uniform, it is
easy to check from their construction that this is the case. As discussed in
the overview, it is possible to use the distance amplification techniques of
[Kop+17] to achieve $c^{3}$-LTCs with distance near $1/2$ (even hitting the GV
bound), but these codes may not be $\varepsilon$-biased and incur a heavy
$\operatorname{poly}(\varepsilon^{-1})$ cost in the query complexity. We will
take a different amplification strategy that avoids these issues almost
entirely at the cost of a small polynomial blowup in rate. The idea is to
concatenate our amplification procedure in Theorem 10.25 with the Hadamard
code:

$Had:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}^{2^{k}},\;\alpha\overset{Had}{\mapsto}\langle\alpha,\cdot\rangle$

We denote the resulting code (the image of this map), by $C_{\text{Had}}$.

The Hadamard code comes with three properties critical to our construction.
First, it is easy to check that the code is binary, linear, and perfectly
balanced ($0$-biased). Second, it is a classical result that the Hadamard code
is an excellent LTC:

######  Theorem 10.28 ([BLR90]).

The Hadamard code is a uniform $(3,1)$-LTC.

Finally, it is well-known folklore (and an easy exercise) to show the Hadamard
code is locally decodable. We will not go into the formal details of locally
decodable codes, but it suffices to say there is a randomized algorithm
$Dec:\mathbb{F}_{2}^{2^{k}}\times[k]\to\mathbb{F}_{2}$ which given a word $y$
such that $d(y,C_{\text{Had}})<\frac{1}{4}$ and a coordinate $i$, queries only
$2$ bits of $y$ and outputs the correct decoding with probability proportional
to its distance from the code:

$\operatorname*{\mathbb{P}}[Dec(y,i)\neq x_{i}]\leqslant 2d(y,C_{\text{Had}})$
(10.4)

where $x=Had^{-1}(y)$ is the pre-image of the unique closest codeword to $y$.

Note that this is essentially the same property we used in Theorem 10.25 in
decoding the ABNNR-encoding. We will show that concatenating with the Hadamard
code similarly allows us to amplify the bias and distance of the base code
while only incurring constant blow-up in query complexity and logarithmic loss
in soundness.

######  Proposition 10.29 (The Base Code).

For every $\varepsilon>0$ there is an explicit infinite family of uniform,
$\varepsilon$-biased, linear
$(\operatorname{poly}(\varepsilon),\frac{1}{2}-\varepsilon)_{2}$-codes that
are $(O(1),\log^{-1}(1/\varepsilon)))$-locally testable. Moreover, there
exists $t<1$ such that these codes are uniquely decodable up to radius $t$ in
time $n\exp(\operatorname{poly}(\varepsilon^{-1}))$.

###### Proof.

We apply Theorem 10.25 to [Din+22]’s LTCs using the complex $X=W_{G}$
generated by length $k=O(\log(1/\varepsilon))$ random walks on any constant
degree, regular $\frac{1}{2}$-spectral expander $G$ (such expanders are known
to exist for any $n$, see e.g. [Alo21]). This results in a
$\operatorname{poly}(\varepsilon)$-rate code with distance at least
$1-\frac{\varepsilon}{2}$ by the classical expander hitting set lemma [HLW06]
which states that for any set $T\subset\X[1]$ of measure $\rho$

$\operatorname*{\mathbb{P}}_{(s_{1},\ldots,s_{k})\in\X[k]}[|\\{s_{1},\ldots,s_{k}\\}\cap
T|=0]\leqslant\rho\left(\frac{1+\rho}{2}\right)^{k-1}.$ (10.5)

The argument is then as in Corollary 10.24. Finally by Theorem 10.25 this
encoding has a uniform $(c,\frac{c^{\prime}}{\log(1/\varepsilon)})$-local
tester for some universal constants $c,c^{\prime}>0$.

The key step is now to concatenate this resulting family with the Hadamard
code:

$\mathcal{C}\coloneqq Had(E_{X}(C)),$

where the Hadamard encoding is applied pointwise to each symbol in $E_{X}(C)$.
This encoding maintains linearity and decreases the rate by a factor of at
most $2^{k}=\operatorname{poly}(\varepsilon)$. To compute the bias, observe
that since the Hadamard code is perfectly balanced, every non-zero symbol of a
word $w\in E_{X}(C)$ contributes 0 to the bias so in the worst case we have

$\displaystyle bias(\mathcal{C})\leqslant\max_{c\in
E_{X}(C)\setminus\\{0\\}}\\{wt(c)\cdot 0+(1-wt(c))\cdot 1\\}\leqslant
1-d(E_{X}(C))\leqslant\varepsilon,$

where $wt(c)$ denotes the normalized hamming weight (fraction of non-zero
elements in $c$).

We now argue that this concatenation has a uniform local tester. Write $q=c$
and $s=\frac{c^{\prime}}{\log(1/\varepsilon)}$ and recall $E_{X}(C)$ has a
uniform $(q,s)$-local tester (which we’ll refer to as the “base tester”) which
requests only a single bit of each queried symbol. We’ll denote these requests
as pairs $(x,i)\in\X[k-1]\times[k]$. Our testing procedure follows a similar
form as in Theorem 10.25. Namely given a potential word $y$:

  1. 1.

Draw a uniformly random $x\in X$, and run the Hadamard test on $y(x)$.

  2. 2.

For each $(x,i)$ requested by the base tester, run the Hadamard decoder on
$y(x)$ at coordinate $i$.

  3. 3.

Run the base tester on the output

The test is complete by construction, and makes at most $2q+3$ queries (two
for each run of the local decoder, and three for the initial Hadamard test).
Soundness follows along the same lines as Theorem 10.25. We first argue that
the word $y$ must be close to a cartesian product of Hadamard codewords (else
Step 1 rejects). We then argue that the decoding succeeds with high
probability, and the decoded word must be far from the base code (else $y$
itself would be close to $\mathcal{C})$, so the base tester rejects with good
probability.

Formally, let $y\in(\mathbb{F}_{2}^{2^{k}})^{X}$ satisfy
$dist(y,\mathcal{C})=\tau$. We argue that the above procedure rejects with
probability at least $\frac{s\tau}{4q}$. To see this, first observe we can
assume the word $y$ is $1-\frac{s\tau}{4q}$ close from being a product of
Hadamard codewords. Otherwise Step 1 rejects with probability at least
$\frac{s\tau}{4q}$ since

$\operatorname*{\mathbb{P}}[\text{Step 1
Rejects}]\geqslant\mathbb{E}_{x}[dist(y(x),C_{Had})]=dist\left(y,\prod_{X}C_{Had}\right).$

Fix some $y_{\text{had}}\in\prod_{X}C_{Had}$ which minimizes the distance from
$y$ and denote the set of ‘corrupted’ coordinates of $y$ to be

$B\coloneqq\left\\{x\in
X:dist\left(y(x),C_{\text{Had}}\right)\geqslant\frac{1}{4}\right\\}.$

Note that the measure of $B$ is at most $\frac{s\tau}{q}$, since the closeness
of $y$ to $\prod C_{\text{Had}}$ is violated otherwise.

Define set of ‘valid’ decodings of $y$ to be strings in
$(\mathbb{F}_{2}^{k})^{X}$ whose encodings match $y_{\text{had}}$ on all
uncorrupted coordinates:

$Y_{\text{dec}}\coloneqq\left\\{y_{\text{dec}}\in(\mathbb{F}_{2}^{k})^{X}:\forall
x\in\bar{B},Had(y_{\text{dec}}(x))=y_{\text{had}}\right\\}.$

Note that when we re-encode any $y_{\text{dec}}\in Y_{\text{dec}}$, it will be
at distance at most $\frac{s\tau}{q}$ from $y$ since:

$\displaystyle dist(Had(y_{\text{dec}}),y)$ $\displaystyle\leqslant
dist(Had(y_{\text{dec}}),y_{\text{had}})+dist(Had(y_{\text{had}}),y)$
$\displaystyle\leqslant(\operatorname*{\mathbb{P}}[B]\cdot\frac{1}{2}+\operatorname*{\mathbb{P}}[\bar{B}]\cdot
0)+\frac{s\tau}{4q}$ $\displaystyle\leqslant\frac{s\tau}{q}.$

We now argue that Step 2 correctly decodes to some $y_{\text{dec}}\in
Y_{\text{dec}}$ with high probability. Since decoding always ‘succeeds’ on
coordinates in $B$ (since any decoded value is accepted), the worst case is
when $B=\emptyset$ and $y_{dec}$ is the pre-image of the unique closest word
in every coordinate. In this case, local decodability of the Hadamard code
(10.4) promises the probability any fixed query $(x,i)$ fails to decode to
$y_{dec}(x)_{i}$ is at most

$\mathbb{E}_{x}[2dist(y(x),C_{Had})]\leqslant
2dist\left(y,\prod_{X}C_{\text{Had}}\right)\leqslant\frac{s\tau}{2q}.$

Union bounding over all $q$ queries, we decode to $y_{\text{dec}}$ except with
probability $\frac{s\tau}{2}$.

Finally, we argue any $y_{\text{dec}}\in Y_{\text{dec}}$ must be
$\frac{3}{4}\tau$-far from $E_{X}(C)$, in which case the base tester rejects
with probability at least $\frac{3}{4}s\tau-\frac{s\tau}{2}=\frac{s\tau}{4}$
by a union bound. This simply follows from the fact that if $y_{\text{dec}}$
were $\frac{3}{4}\tau$-close to $E_{X}(C)$, then there exists $w\in E_{X}(C)$
such that

$\displaystyle dist(Had(w),y)$ $\displaystyle\leqslant
dist(Had(w),Had(y_{\text{dec}}))+dist(Had(y_{\text{dec}}),y)$
$\displaystyle\leqslant dist(w,y)+\frac{s\tau}{q}$
$\displaystyle\leqslant\tau$

where the second inequality comes from observing that the encodings of $w$ and
$y_{\text{dec}}$ are the same on any symbol on which they agree, and can only
improve in distance when they differ.242424Technically we’ve also used that
$q\geqslant 4$ and $s\leqslant 1$ here, which follow from the parameters of
[Din+22].

It is left to show our concatenated family has an efficient unique decoder. It
is a classical fact that concatenating codes with efficient unique decoding at
radii $t_{\text{inner}}$ and $t_{\text{outer}}$ gives a code with an efficient
unique decoder at radius $t_{\text{inner}}t_{\text{outer}}$ simply by running
the inner decoder on every inner symbol, then running the outer decoder on the
result [For65]. In particular decoding at this distance is successful since if
a true word $m$ is corrupted in at most a $t_{\text{inner}}t_{\text{outer}}$
fraction of its coordinates, no more than a $t_{\text{outer}}$ fraction of
inner codewords can have a $t_{\text{inner}}$ fraction of corruptions. Thus
running the inner decoder results in the correct word except in at most a
$t_{\text{outer}}$ fraction of outer coordinates, which is then successfully
decoded by the outer decoder.

We can decode over each Hadamard symbol up to radius $t^{\prime}<\frac{1}{4}$
by brute force in $\exp(\operatorname{poly}(\varepsilon^{-1}))$ time (and
otherwise output some fixed word, say 0, beyond this radius). $E_{X}(C)$ can
be efficiently decoded up to some constant radius $t$ by taking the majority
vote over each coordinate, then running the base decoder on $C$ (see e.g.
[Din+18]). This process takes time
$n\exp(\operatorname{poly}(\varepsilon^{-1}))+O(n)$, for a total time of
$n\exp(\operatorname{poly}(\varepsilon^{-1}))$ as desired. ∎

Finally, we argue these base codes can be amplified to large alphabet LTCs
with near optimal distance.

######  Corollary 10.30 (Large Distance c3-LTCs).

For all large enough $k\in\mathbb{N}$ and all $\varepsilon>0$, there exists an
infinite family of $\mathbb{F}_{2}$-linear $(r,d)_{|\Sigma|}$-codes that are
$(q,s)$-locally testable for:

$r=\varepsilon^{O(k)},\quad d=1-2^{-k}-\varepsilon,\quad|\Sigma|=2^{k},\quad
q=O(1),\quad s=O\left(\frac{1}{k\log(\frac{1}{\varepsilon})}\right)$

###### Proof.

We start with the explicit family of base codes given in Proposition 10.29
with $q=O(1)$ queries, distance $\frac{1}{2}-\frac{\varepsilon}{4}$, and rate
$\operatorname{poly}(\varepsilon)$. For a given code $C$ in the family of
blocklength $n$, let $X$ be the collection of length-$k$ walks on any explicit
degree $\frac{\varepsilon}{2}$-expander of degree $O(\varepsilon^{-2})$ on $n$
vertices (such graphs exist for any large enough $n$ [Alo21]). The size of
$\X[k-1]$ is $O(\frac{n}{\varepsilon^{2k}})$, and the expander hitting-set
lemma (Equation (10.5)) ensures the distance of $E_{X}(C)$ is at least

$1-\left(\frac{1}{2}+\frac{\varepsilon}{2}\right)^{k}\geqslant
1-2^{-k}-\varepsilon.$

Finally, since the base code’s tester is uniform, local testability follows
from Theorem 10.25. ∎

It is worth comparing Theorem 10.25 to the distance amplification for LTCs of
Kopparty, Meir, Ron-Zewi, and Saraf [Kop+17], who also analyzes local
testability of distance-amplified codes via a related construction of Alon and
Luby [AL96]. Their work largely focuses on achieving near-optimal rate-
distance trade-off: they achieve the singleton bound over large alphabet codes
and the GV-bound over $\mathbb{F}_{2}$. In comparison Theorem 10.25 has worse
rate than their construction, but makes up for this with exponentially better
alphabet size and local testability. Quantitatively, to achieve distance
$1-\beta$, [Kop+17]’s codes require alphabet size
$2^{\operatorname{poly}(1/\beta)}$ and lose $\operatorname{poly}(1/\beta)$
factors in the testing parameters, while ours have the optimal
$\beta^{-1}$-dependence in the former and lose only logarithmically in the
latter.

###  10.6 List-Decoding ABNNR

In this section, we show that the codes in Corollary 10.30 are efficiently
list-decodable, completing the proof of Theorem 10.21. Efficient list-decoding
of the ABNNR construction was first considered by Dinur, Harsha, Kaufman,
Livni-Navon, and TaShma [Din+18], who gave an algorithm for the construction
instantiated on HDX. After [Din+18]’s work, Alev, Jeronimo, Quintana,
Srivastava, and Tulsiani [Ale+20] showed it possible to efficiently list
decode a closely related construction called a direct sum code over some
relaxed families of splitting trees (including HDX and expander walks). Using
a reduction to direct sum, they also recover the parameters of [Din+18]’s
ABBNR-codes on HDX as well.

In this section, we give an efficient list-decoding algorithm for the ABNNR-
construction on complexes satisfying a slightly strengthened variant of
splittability that ensures the complex can be “split” at any coordinate. We
refer to this notion as complete splittability.

######  Definition 10.31 (Complete Splittability).

A $d$-uniform partite complex $X$ is called completely $\lambda$-splittable if
for all $i\in[d]$:

$\lambda_{2}(S_{[1,i],[i+1,d]})\leqslant\lambda$

where we recall $S_{[1,i],[i+1,d]}$ is the ‘swap walk’ adjacency operator
between $X[{[1,i]}]$ and $X[{[i+1,d]}]$.

Complete splittability sits in-between tuple-splitting trees and partite HDX,
and is closely related to notions of splittability defined in more recent
works on direct-sum decoding [JST21, BD22] (in particular it is equivalent to
the definition introduced in the former, see Appendix F for details). We can
now state the main result of the subsection:

######  Theorem 10.32 (List Decoding on Completely Splittable Complexes).

For any $t<1/2$, let $C_{0}$ be a binary code with blocklength $n$,
$\text{bias}(C_{0})\leqslant 1-2t$, and which is unique-decodable to radius
$t$ in time $\mathcal{T}_{0}$. Let $X\subset[n]^{k}$ be a homogenous,
completely $\lambda$-splittable complex, and $C=E_{X}(C_{0})$ its ABNNR
encoding. Let $d(C)=1-\varepsilon$ and $\tau>0$ be any value satisfying

$\tau\geqslant\max\left\\{\sqrt{\varepsilon},4\sqrt{(1-2t)^{i}+2\lambda},\sqrt{2^{21}\lambda
k^{3}},8\left(1-t\right)^{i/2}\right\\}$

for $i=\frac{k}{2}-\sqrt{k\log(\frac{2}{\tau})}$. There exists a randomized
algorithm, which given $\tilde{y}\in(\mathbb{F}_{2}^{k})^{X}$ recovers the
list

$\mathcal{L}_{\tau}(\tilde{y})=\left\\{y\in C:d(\tilde{y},y)\leqslant
1-\tau\right\\}$

with probability
$1-\frac{\tau-\varepsilon}{\varepsilon(\tau^{2}-\varepsilon^{2})}2^{-\Omega(n/t^{2})}$
in time
$\tilde{O}(\frac{\tau-\varepsilon}{\tau^{2}-\varepsilon^{2}}\exp(\log(1/t)\exp(k^{3}/\tau^{2}))(|X|+\mathcal{T}_{0}))$.
Moreover, the number of such codewords is at most:

$|\mathcal{L}_{\tau}(\tilde{y})|\leqslant\frac{\tau-\varepsilon}{\tau^{2}-\varepsilon^{2}}.$

The proof of Theorem 10.32 goes via reduction to direct sum decoding. The
direct sum encoding of a code $C$ on a complex $X$ simply concatenates the
ABNNR-encoding with $XOR:\mathbb{F}_{2}^{k}\to\mathbb{F}_{2}$, that is
$dsum_{X}(C)\coloneqq XOR(E_{X}(C))$ (where XOR applied pointwise, similar to
in the Hadamard concatenation in the prior section). Most of the work in
proving Theorem 10.32 is already done via [JST21, BD22]’s direct sum decoder
for completely splittable complexes:

######  Theorem 10.33 (List Decoding Direct Sum [JST21, BD22]).

For any $t<1/2$, let $C_{0}$ be a binary code with blocklength $n$,
$\text{bias}(C_{0})\leqslant 1-2t$, and which is unique-decodable to radius
$t$ in time $\mathcal{T}_{0}$. Let $X\subset[n]^{k}$ be a homogenous,
completely $\lambda$-splittable complex, and $C=\text{dsum}_{X}(C_{0})$ be its
direct sum encoding. Let $\varepsilon=bias(C)$ and $\beta>0$ be such that

$\beta\geqslant\max\left\\{\sqrt{\varepsilon},\sqrt{2^{20}\lambda
k^{3}},2\left(1-t\right)^{k/2}\right\\}.$

There exists a randomized algorithm which given
$\tilde{y}\in\mathbb{F}_{2}^{X}$ recovers the list

$\mathcal{L}^{X,(sum)}_{\beta}(\tilde{y})=\left\\{x\in
C_{0}:d(\tilde{y},dsum_{X}(x))\leqslant\frac{1}{2}-\beta\right\\}$

with probability $1-\frac{1}{\varepsilon}2^{-\Omega(n/t^{2})}$ in time
$\tilde{O}(\exp(\log(t)\exp(\frac{k^{3}}{\beta^{2}}))|X|+\mathcal{T}_{0})$.
Moreover, the list has at most

$|\mathcal{L}^{X,(sum)}_{\beta}(\tilde{y})|\leqslant\frac{1}{\varepsilon}$

codewords.

We remark that the requirement on the unique decoder radius in [JST21, BD22]
is slightly more strict as stated, but one can easily modify parameters in
their proof to achieve the above. We now prove Theorem 10.32 by reduction to
Theorem 10.33.

###### Proof of Theorem 10.32.

We appeal to a simple variant of the reduction of [Ale+20]. Given a potential
word $\tilde{y}\in(\mathbb{F}_{2}^{k})^{X}$ at distance
$d(\tilde{y},C)=1-\tau$, we claim the following process is an efficient list-
decoder.

  1. 1.

For every $F\subseteq[d]$, apply Theorem 10.33 to $XOR(\tilde{y}|_{F})$ on
$dsum_{X^{F}}(C)$ with $\beta=\tau/4$ to get:

$\mathcal{L}^{pot}_{\beta}(\tilde{y})\coloneqq\bigcup_{F\subseteq[d+1]}\mathcal{L}^{X^{F},(sum)}_{\beta}(\tilde{y})$

  2. 2.

Prune any decodings that are far from $\tilde{y}$:

$\mathcal{L}_{\tau}(\tilde{y})\coloneqq\left\\{E_{X}(x):x\in\mathcal{L}_{\beta}^{pot}(\tilde{y}),\leavevmode\nobreak\
d(E_{X}(x),\tilde{y})\leqslant 1-\tau\right\\}.$

To prove this procedure indeed gives a valid list-decoding we will use the
fact that any projection of a splittable complex, in particular each $X^{F}$
above, is also splittable.

######  Claim 10.34.

Let $X\subset[n]^{d}$ be a homogeneous, completely $\lambda$-splittable
complex. Then for any $F\subseteq[d]$, $X^{F}$ is homogeneous and completely
$\lambda$-splittable.

The proof follows from the inheritance of expansion under projection, and is
defered to Appendix F.

We now prove the output list $\mathcal{L}_{\tau}$ is exactly the set of
codewords at distance at most $1-\tau$ from $C$. Recall that our base code is
assumed to be at most $(1-2t)$-biased. By bias amplification lemma for
splitting trees (Proposition 10.13) and Claim 10.34, we have that for any
$X^{F}$, the bias of $dsum_{X^{F}}(C)$ is at most $(1-2t)^{|F|}+2\lambda$. As
such, our choice of $\beta=\tau/4$ satisfies the conditions of Theorem 10.33
whenever $i\leqslant|F|\leqslant k$ (for $i$ as in the Theorem statement). Let
$y\in E_{X}(C)$ be a codeword at distance at most $1-\tau$ from $\tilde{y}$,
then we have

$\operatorname*{\mathbb{P}}[\tilde{y}_{s}=y_{s}]=\mathbb{E}_{s}\left[\mathbb{E}_{F\in\mathbb{F}_{2}^{k}}[\chi_{F}(\tilde{y}_{s}+y_{s})]\right]\geqslant\tau,$

where $\chi_{F}(y)=(-1)^{\langle F,y\rangle}$ are the standard characters. By
averaging and Chernoff, there must exist
$|F|\geqslant\frac{k}{2}-\sqrt{k\log(2/\tau))}$ such that

$\mathbb{E}_{s}\left[\chi_{F}(\tilde{y}_{s})\chi_{F}(y_{s})\right]\geqslant\tau/2,$

which is equivalent to the statement that the distance of $\tilde{y}|_{F}$
from $y|_{F}$ is at most $\frac{1}{2}-\frac{\tau}{4}=\frac{1}{2}-\beta$ in the
direct sum encoding on $X^{F}$. Since $X^{F}$ is homogeneous and completely
$\lambda$-splittable, by Theorem 10.33 we have that the decoding of $y$
appears in $\mathcal{L}_{pot}(\tilde{y})$ except with probability
$\frac{1}{\varepsilon}\exp(n/t^{2})$. By the Johnson bound (see e.g.
[Din+18][Theorem 2.15]), there can be at most
$\frac{\tau-\varepsilon}{\tau^{2}-\varepsilon^{2}}$ such codewords $y$ close
to $\tilde{y}$, so union bounding over these gives that all valid codewords
are in the list with the desired probability. Finally, all extraneous
decodings are removed in the second step, which completes correctness of the
procedure.

Running time follows immediately from the fact that we have run the direct sum
decoder at most $2^{k}$ times, and the resulting potential list has at most
$\exp(k)$ potential codewords by the Johnson bound and our choice of
$\beta=\tau/4$, each of which can be pruned in $O(k|X|)$ time. ∎

Finally, we instantiate this result on expander walks to complete the proof of
Theorem 10.21.

######  Corollary 10.35.

The family of codes in Corollary 10.30 is
$(1-2^{-\Omega(k)},\frac{1}{2^{O(k)}})$ efficiently list-decodable with
confidence $2^{-\Omega(n-k)}$.

###### Proof.

Since [JST21] prove that walks on an $\lambda$-expander are homogeneous and
completely $\lambda$-splittable, it is enough to ensure the parameter $\tau$
in Theorem 10.32 can be set to $2^{-\Omega(k)}$. Recalling that the base code
of this construction is $\varepsilon$-biased and uniquely decodable in linear
time up to constant radius, and that the encoding has distance at least
$1-2^{-k}-\varepsilon$, as long as $\varepsilon\leqslant\exp(-\Omega(k))$ one
can easily check it is possible to take $\tau=\exp(-\Omega(k))$ and
$\frac{\tau-\varepsilon}{\tau^{2}-\varepsilon^{2}}=2^{-O(k)}$ satisfies all
conditions of Theorem 10.32. ∎

###  10.7 Toward Lossless Amplification from HDX?

Our expander-based construction experiences polylogarithmic decay in soundness
with the alphabet size. This is exponentially better than prior methods, but
it is plausible the decay could be avoided entirely. In this section, we
propose an approach toward such ‘lossless’ amplification via the ABNNR-
Encoding on an HDX.

Instantiating Theorem 10.25 directly on an HDX does actually slightly improve
soundness over Theorem 10.21, but the loss of $\frac{1}{k}$ in the dimension
of the complex is inherent to our approach, no matter the instantiation. The
reason is that our method only simulates the base tester a single time. As a
result, the rejection probability will only scale with the distance of the
decoded word from the base code. On the other hand, because $X$ amplifies this
distance by a factor of $k$, this results in an unavoidable loss in soundness.

There is a natural approach to fixing this issue: simulate the base tester
“$k$ times in parallel,” analogous to Raz’s parallel repetition theorem
[Raz95] and its de-randomized variants in agreement testing [IKW12, DM11,
DD23a, BM23a]. Indeed on the complete complex, this approach can actually be
carried out successfully:

######  Theorem 10.36 (Parallel LTC Amplification).

Let $C$ be a uniformly $(q,s)$-locally testable
$(r,\frac{1-\varepsilon}{2})_{2}$-code of blocklength $n$ and
$X=\binom{[n]}{k}$. Then $E_{X}(C)$ is a uniformly
$(q^{\prime},s^{\prime})$-locally testable
$(r^{\prime},d^{\prime})_{|\Sigma|}$-code for:

$r^{\prime}=\frac{r}{n^{k-1}},\quad
d^{\prime}=1-\frac{1}{2^{k}}\left(1+\varepsilon\right)^{k}-o_{n}(1),\quad|\Sigma|=2^{k},\quad
q^{\prime}=q+2,\quad s^{\prime}=cs$

where $c>1$ is some universal constant (independent of $k$).

###### Proof.

Rate and alphabet are immediate from construction, and distance follows from
(near)-independence of $\binom{[n]}{k}$. For local testability, we rely on the
following agreement theorem of Dinur and Steurer:

######  Claim 10.37 ([DS14]).

There exists a two query agreement test on $\binom{[n]}{k}$ and a constant
$c\geqslant 1$ such that252525We remark that formally Dinur and Steurer
consider $[n]^{k}$, but their techniques transfer to this setting (formally,
see e.g. [DD19] for the quoted result).

$Agree_{0}(\mathcal{F})\geqslant 1-\varepsilon\quad\implies\quad
dist(\mathcal{F},g_{\text{maj}})\leqslant c\varepsilon$

With this in hand the proof is similar to Theorem 10.25. For $k$ independent
runs of the base tester $\mathcal{T}_{C}$, denote the requested symbols by
$\\{x^{(i)}_{j}\\}_{j\in[q],i\in[k]}$ and write
$s_{j}\coloneqq\\{x_{j}^{(1)},\ldots,x_{j}^{(k)}\\}\in\binom{[n]}{k}$. Given a
word $f$, our tester performs the following two-step procedure:

  1. 1.

Run the Dinur-Steurer test on $f$

  2. 2.

For every $i\in[q]$:

     * –

For each $j\in[k]$, denote the ‘decoded’ plurality function at $x^{(i)}_{j}$
as $g_{\text{dec}}(x_{j}^{(i)})=f_{s_{j}}(x_{j}^{(i)})$

     * –

Run $\mathcal{T}_{C}$ on
$g_{\text{dec}}(x^{(i)}_{1}),\ldots,g_{\text{dec}}(x^{(i)}_{q})$

The tester is complete and makes $q+2$ queries by construction. The proof of
soundness is very similar to Theorem 10.25, so we give a shortened explanation
here. Assuming $dist(f,E_{X}(C))=\delta$, we need to show our test rejects