# Sparse High Dimensional Expanders via Local Lifts

Inbar Ben Yaacov Department of Computer Science, Weizmann Institute of
Science, Israel. email<EMAIL_ADDRESS>This project has
received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (grant agreement No.
819702) and from the Simons Foundation Collaboration on the Theory of
Algorithmic Fairness. Yotam Dikstein Institute for Advanced Study, USA. email:
<EMAIL_ADDRESS>This material is based upon work supported by the
National Science Foundation under Grant No. DMS-1926686. Gal Maor Tel Aviv
University, Israel. email<EMAIL_ADDRESS>Supported by Gil Cohen’s
ERC grant 949499.

###### Abstract

High dimensional expanders (HDXs) are a hypergraph generalization of expander
graphs. They are extensively studied in the math and TCS communities due to
their many applications. Like expander graphs, HDXs are especially interesting
for applications when they are bounded degree, namely, if the number of edges
adjacent to every vertex is bounded. However, only a handful of constructions
are known to have this property, all of which rely on non-trivial algebraic
techniques. In particular, no random or combinatorial construction of bounded
degree high dimensional expanders is known. As a result, our understanding of
these objects is limited.

The degree of an $i$-face in an HDX is the number of $(i+1)$-faces that
contain it. In this work we construct complexes whose higher dimensional faces
have bounded degree. This is done by giving an elementary and deterministic
algorithm that takes as input a regular $k$-dimensional HDX $X$ and outputs
another regular $k$-dimensional HDX $\widehat{X}$ with twice as many vertices.
While the degree of vertices in $\widehat{X}$ grows, the degree of the
$(k-1)$-faces in $\widehat{X}$ stays the same. As a result, we obtain a new
‘algebra-free’ construction of HDXs whose $(k-1)$-face degree is bounded.

Our construction algorithm is based on a simple and natural generalization of
the expander graph construction by Bilu and Linial [BL06], which build
expander graphs using lifts coming from edge signings. Our construction is
based on _local lifts_ of high dimensional expanders, where a local lift is a
new complex whose top-level links are lifts of the links of the original
complex. We demonstrate that a local lift of an HDX is also an HDX in many
cases.

In addition, combining local lifts with existing bounded degree constructions
creates new families of bounded degree HDXs with significantly different links
than before. We use this technique to construct bounded degree high
dimensional expanders with links that have arbitrarily large diameters.

##  1 Introduction

Expander graphs are graphs that are well connected. These objects are studied
extensively in computer science and mathematics [HLW06], and since their
discovery they have found numerous applications in complexity [Din07, Rei08],
coding theory [SS96, Ta-17, Din+22], derandomization [HLW06, Gol11] and more.
Most of these applications rely on families of expander graphs that have a
bounded degree. It is well known that random regular graphs are expanders, and
many explicit bounded degree constructions are also in hand [MAR73, LPS88,
RVW02, BL06, MSS15].

Recently, the study of _high dimensional expanders_ (HDXs) emerged (see
surveys [Lub18, GK23]). These are hypergraph analogues of expander graphs.
While the full potential of high dimensional expanders is yet to be
discovered, they are already important objects of study. High dimensional
expanders, and especially bounded degree high dimensional expanders 111A
family of HDXs is called _bounded degree_ if there is some $M>0$ so that all
vertices in every HDX in the family have degree at most $M$. have already
yielded exciting applications in various areas such as locally testable codes
[Din+22, PK22, DLZ23], quantum complexity [ABN23], sampling and Markov chains
[Ana+19], agreement testing [DK17, DDL24, BLM24], high dimensional geometry
and topology [Gro10, Fox+12] and random (hyper)graph theory [LM06, MW09].

The specific family of high dimensional expanders used in many of the
aforementioned applications is tailor-made to satisfy other desired
properties, in addition to high dimensional expansion. For example, the local
neighborhoods in the high dimensional expanders used in [Din+22, PK22, DLZ23]
are tailored so that one can define a small locally testable code on them; the
high dimensional expanders in [Gro10, DDL24, BLM24] also have a vanishing
$1$-cohomology over certain group coefficients.

However, constructing bounded degree high dimensional expanders (for
arbitrarily small spectral expansion of the links) is still a serious
challenge. No random model for bounded degree high dimensional expanders is
known, and all deterministic constructions known use non-trivial algebraic
techniques. The fact that we have only a handful of bounded degree
constructions to choose from, makes these objects difficult to understand and
to work with. We believe that many further applications await us once we learn
how to diversify these constructions, in the same way that many of the above-
mentioned applications of expander graphs grew out of more varied expander
constructions that were discovered.

Nowadays, all known constructions of HDXs rely on non-trivial algebraic
techniques, including quotients of the Bruhat Tits buildings [Bal00, CSŻ03,
Li04, LSV05, Dik22, DDL24, BLM24] and coset complexes [KO18, FI20, OP22].
There have been attempts at constructing bounded degree HDXs with
combinatorial tools, but all these constructions fall short either in bounded
degreeness [Gol23, Liu+23] or in their local spectral expansion [Con19, CTZ20,
CLY20, LMY20, Gol21].

In particular, it is an important open question whether an algorithm à la Zig-
Zag product [RVW02] exists for bounded degree high dimensional expanders. That
is, an algorithm that given a bounded degree high dimensional expander as
input, outputs another high dimensional expander with more vertices and the
same bound on the degree and spectral expansion.

As an intermediate result, in this work we develop an algorithm that takes a
high dimensional expander as input, and outputs another high dimensional
expander with more vertices, the same bound on spectral expansion and the same
bound on _the degree of high dimensional faces_ (but not on the degree
vertices). This algorithm is entirely combinatorial, relying only on the
theory of graph covers initiated by [AL02, BL06]. While families of complexes
constructed via such an algorithm are not sufficient for applications that
require the vertex degree to be bounded, we view this as a stepping stone
towards an ‘algebra free’ construction of bounded degree HDXs.

###  1.1 Preliminaries on High Dimensional Expanders

To better understand our results, let us introduce some standard definitions
and notation on simplicial complexes (see Subsection 2.3 for a more elaborated
definitions). A simplicial complex is a hypergraph that is downwards closed to
containment. A simplicial complex is $k$-dimensional if the largest hyperedge
in the complex is of size $(k+1)$. We denote by $X(\ell)$ the sets (aka faces)
of size $\ell+1$. Let $X$ be a $k$-dimensional simplicial complex.

The degree of a face $\sigma\in X(\ell)$, is
$d(\sigma)\vcentcolon=\lvert\left\\{\tau\in X(\ell+1)\left|\;\vphantom{\tau\in
X(\ell+1)\tau\supseteq\sigma}\right.\tau\supseteq\sigma\right\\}\rvert$. A
family of complexes $\left\\{X_{i}\right\\}_{i=0}^{\infty}$ is _$\ell$
-bounded degree_ if there exists an $M>0$ that bounds the degrees of _all
$\ell$-faces_ across _all the complexes simultaneously_. That is, for every
$i$ and any $\sigma\in X_{i}(\ell)$, $d(\sigma)\leqslant M$. We say that a
family of complexes are bounded degree if they are $0$-bounded degree. We say
that a complex is $(d_{0},d_{1},\dots,d_{k-1})$-regular if for every
$\sigma\in X(\ell)$, $d(\sigma)=d_{\ell}$.

In this paper we are mainly interested in the local spectral expansion
definition of high dimensional expanders (see [Lub18] for a survey on other
definitions). For this we need to define ‘links’, the generalization of vertex
neighborhoods in graphs. For a face $\sigma\in X$, the link of $\sigma$ is the
simplicial complex
$X_{\sigma}=\left\\{\tau\setminus\sigma\left|\;\vphantom{\tau\setminus\sigma\sigma\subseteq\tau\in
X}\right.\sigma\subseteq\tau\in X\right\\}$. We will be interested in the
graph structure underlying the complex and its links. The $1$-skeleton of $X$
is the graph whose vertices are $X(0)$ and whose edges are $X(1)$.

######  Definition 1.1 (High dimensional expander).

For $\lambda>0$ we say that $X$ is a $\lambda$-two sided (one sided) high
dimensional expander if for every $\ell\leqslant k-2$ and $\sigma\in X(\ell)$,
the $1$-skeleton of $X_{\sigma}$ is a $\lambda$-two sided (one sided) spectral
expander.

###  1.2 Our Results

Our results are based on the notion of a graph lifts. We say a graph
$\widehat{G}=(\widehat{V},\widehat{E})$ is a lift of a graph $G=(V,E)$ if
there exists a graph homomorphism $\phi:\widehat{V}\to V$ such that for every
$\hat{v}\in\widehat{V}$, the mapping $\phi$ is a bijection on the neighborhood
of $\hat{v}$. Intuitively, a lift of a graph $G$ is a large graph
$\widehat{G}$ that locally looks the same as $G$. Graph lifts are essential in
many constructions of expander graphs [AL02, BL06, MSS15], and our
construction builds on the beautiful work of [BL06]. We elaborate more on this
below.

Our main result is a construction algorithm that maintains both expansion and
the degree of the $(k-1)$-faces of a regular complex. This algorithm takes as
input a $(d_{0},d_{1},\dots,d_{k-1})$-regular $\lambda$-high dimensional
expander $X$, and outputs a $(2d_{0},2d_{1},\dots,2d_{k-2},d_{k-1})$-regular
$\widehat{X}$ with twice as many vertices that is also a $\lambda$-HDX. This
algorithm uses the notion of random lifts [BL06], and in particular, it
requires no algebraic machinery for the construction nor the analysis. More
formally, this is the theorem we prove.

######  Theorem 1.2 (See Theorem 5.2 for a more precise statement).

There exists a randomized algorithm $\mathcal{A}$ that takes as input a
$k$-dimensional complex $X_{0}$ and an integer $i\geqslant 1$, runs in
expected time $\operatorname{poly}((2^{i}|X_{0}(0)|)^{k})$ at most, and
outputs a $k$-dimensional complex $X_{i}$ with $2^{i}|X_{0}(0)|$ vertices. The
algorithm has the following guarantees.

  1. 1.

If $X_{0}$ is a $(d_{0},d_{1},\ldots,d_{k-1})$-regular $\lambda$-two sided
high dimensional expander, then $X_{i}$ is a
$(2^{i}d_{0},\dots,2^{i}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two sided
high dimensional expander where

$\lambda^{\prime}=O\left(\max\left\\{\lambda\left(1+\log\frac{1}{\lambda}\right),\sqrt{\frac{\log^{3}d_{k-1}}{d_{k-1}}}\right\\}\right).$

  2. 2.

For every $\hat{\sigma}\in X_{i}(k-2)$, the link $(X_{i})_{\hat{\sigma}}$ is a
lift of $(X_{i-1})_{\sigma}$ for some $\sigma\in X_{i-1}(k-2)$.

There are various complexes in hand that one can use as the input to this
algorithm. These include the complete complex, the complexes from [LLR19], and
even complexes from bounded degree families that are regular, such as those
constructed by [FI20].

We give two proofs to Theorem 1.2, building on the techniques developed by
[BL06] to analyze lifts in expander graphs, and extend them to high
dimensional expanders.

While most of the work in [BL06] regards random lifts of graphs, they also
show how to deterministically find expander graphs using lifts. Building on
their method, we also give a deterministic algorithm for finding the complexes
in Theorem 1.2, albeit under some more assumptions on the input $X_{0}$. This
provides a _deterministic, polynomial time and elementary_ construction of a
family of $(k-1)$-bounded $k$-dimensional high dimensional expanders.

######  Theorem 1.3 (See Theorem 6.1).

There exists a deterministic algorithm $\mathcal{B}$ that takes as input a
$k$-dimensional complex $X_{0}$ and an integer $i\geqslant 1$, runs in time
$\operatorname{poly}((2^{i}|X_{0}(0)|)^{k})$ at most, and outputs a
$k$-dimensional complex $X_{i}$ with $2^{i}|X_{0}(0)|$ vertices. The algorithm
has the following guarantees.

  1. 1.

If $X_{0}$ is a $(d_{0},d_{1}\ldots,d_{k-1})$-regular $\lambda$-two sided high
dimensional expander, such that $d_{k-1}>2^{10k}$ and
$|X_{0}(k-2)|\leqslant\left(d_{k-2}\right)^{10k}$, then $X_{i}$ is a
$(2^{i}d_{0},\dots,2^{i}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two sided
high dimensional expander where

$\lambda^{\prime}=O\left(2^{5k}\max\left\\{\lambda\left(1+\log\frac{1}{\lambda}\right),\sqrt{\frac{\log^{3}d_{k-1}}{d_{k-1}}}\right\\}\right).$

  2. 2.

For every $\hat{\sigma}\in X_{i}(k-2)$, the link $(X_{i})_{\hat{\sigma}}$ is a
lift of $(X_{i-1})_{\sigma}$ for some $\sigma\in X_{i-1}(k-2)$.

As far as we know, previous constructions rely on deep algebraic tools but are
$0$-bounded degree, with the exception of [LLR19], which is a randomized
construction utilizing Steiner systems constructed in [Kee14].

Not only is our construction deterministic, but it is also simple and
versatile; one can apply it to various kinds of high dimensional expanders,
and the family of HDXs obtained by doing so is changes according to the
initiating HDX given at the beginning of the process.

###  1.3 The Construction

We now dive into the heart of Theorem 1.2. Our construction builds upon the
work of random lifts of graphs studied in [BL06]. Random lifts of expanders
have been subject to extensive research (e.g., [Ami+01, BL06, AKM13, MSS15,
Bor20]). However, in this work, we do not try to lift the complex itself.
Instead, we construct another complex where the _$(k-2)$ -links_ are lifts of
links in the original complex. We call such a complex a _local lift_.

Let us first explain the idea behind the work of [BL06]. Their work suggests a
construction of bounded degree family of expander graphs
$\left\\{G_{i}\right\\}_{i=0}^{\infty}$, where for every $i$, $G_{i+1}$ is a
lift of $G_{i}$. The fact that the maximal degree of $G_{i+1}$ is equal to the
maximal degree of $G_{i}$ promises that the sequence is bounded degree.
Therefore, one only needs to worry about expansion.

The work [BL06] studies random lifts sampled using signings on the edges of a
graph $G=(V,E)$, that is, functions $f:E\to\left\\{\pm 1\right\\}$. Given such
a signing $f$, one can construct the following lift
$\widehat{G}=(\widehat{V},\widehat{E})$ by setting
$\widehat{V}=V\times\left\\{\pm 1\right\\}$ and
$\left\\{(v,i),(u,j)\right\\}\in\widehat{E}$ if $\left\\{v,u\right\\}\in E$
and $i\cdot j=f(\left\\{u,v\right\\})$.

The work of [BL06] analyzes when a lift $\widehat{G}$ obtained by random
signing $f$ is an expander graph. They give a proof (based on the Lovász Local
Lemma) that every expander $G$ has such a “good” signing. They also provide a
deterministic algorithm to construct such a lift using the conditional
probabilities method [AS16].

Our construction generalizes this idea, only instead of lifts coming from edge
signings, we define _local lifts_ coming from _face_ -signings.

Let $X$ be a $k$-dimensional simplicial complex and let $f:X(k)\to\left\\{\pm
1\right\\}$. Define the $k$-dimensional complex $\widehat{X}$ (where $f$ is
implicit in the notation) as a complex whose vertices are
$\widehat{X}(0)=X(0)\times\left\\{\pm 1\right\\}$, and whose $k$-faces are

$\widehat{X}(k)=\left\\{\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{k}^{j_{k}}\right\\}\left|\;\vphantom{\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{k}^{j_{k}}\right\\}\left\\{v_{0},v_{1},\dots,v_{k}\right\\}\in
X(k)\;\hbox{and}\;\prod_{i=0}^{k}j_{i}=f(\left\\{v_{0},v_{1},\dots,v_{k}\right\\})}\right.\left\\{v_{0},v_{1},\dots,v_{k}\right\\}\in
X(k)\;\hbox{and}\;\prod_{i=0}^{k}j_{i}=f(\left\\{v_{0},v_{1},\dots,v_{k}\right\\})\right\\}.$

For $1\leqslant\ell\leqslant k-1$ the $\ell$-faces are independent of the
second coordinate, that is,

$\widehat{X}(\ell)=\left\\{\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{\ell}^{j_{\ell}}\right\\}\left|\;\vphantom{\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{\ell}^{j_{\ell}}\right\\}\left\\{v_{0},v_{1},\dots,v_{\ell}\right\\}\in
X(\ell)}\right.\left\\{v_{0},v_{1},\dots,v_{\ell}\right\\}\in
X(\ell)\right\\}.$

Obviously, the underlying graph of $\widehat{X}$ is _not_ a lift of the
underlying graph of $X$. Indeed, the degree of each vertex is doubled.
However, for every $\hat{\sigma}\in\widehat{X}(k-2)$, we show that
$\widehat{X}_{\hat{\sigma}}$ is isomorphic to a lift of $X_{\sigma}$ (where
$\sigma=\left\\{v\left|\;\vphantom{vv^{j}\in\hat{\sigma}}\right.v^{j}\in\hat{\sigma}\right\\}$).

Indeed, let us assume for simplicity that $k=2$. Consider the link of a vertex
$v^{j}\in\widehat{X}(0)$ and define the function $g:X_{v}(1)\to\left\\{\pm
1\right\\}$ by $g(uw)=j\cdot f(uw)$. We claim that $\widehat{X}_{v^{j}}$ is
the cover $g$ induces on $X_{v}$. It is easy to see that its vertices are
$\widehat{X}_{v^{j}}(0)=X_{v}(0)\times\left\\{\pm 1\right\\}$, since the
vertices in $\widehat{X}_{v^{j}}$ correspond to edges in $\widehat{X}(1)$.
These are precisely all $u^{1},u^{-1}$ where $u\in X_{v}(0)$.

The edges are more delicate. Edges
$\left\\{u^{j^{\prime}},w^{j^{\prime\prime}}\right\\}\in\widehat{X}_{v^{j}}(1)$
correspond to triangles
$\left\\{v^{j},u^{j^{\prime}},w^{j^{\prime\prime}}\right\\}\in\widehat{X}$.
Indeed, such a triangle is in $\widehat{X}$ if and only if:

  1. 1.

$\left\\{u,w\right\\}\in X_{v}(1)$ and,

  2. 2.

$j\cdot j^{\prime}\cdot j^{\prime\prime}=f(\left\\{v,u,w\right\\})$.

The second item occurs if and only if $j\cdot j^{\prime}\cdot
j^{\prime\prime}=g(uw)$. Hence, $\widehat{X}_{v^{j}}$ is the cover $g$ induces
on $X_{v}$.

As mentioned above, we give two proofs that signings $f$ so that $\widehat{X}$
is a high dimensional expander exist. The first proof is based on the Lovász
Local Lemma and follows the argument in [BL06, Lemma 3.3], and generalizes it
so that multiple links may be taken into account simultaneously. The second
proof is based on a different way to use the Lovász Local Lemma (together with
other results from [BL06]) which we find simpler, to deduce high dimensional
expansion. This proof, while more restrictive on the link sizes, can be
combined with the algorithmic version of the Lovász Local Lemma [MT10], to
prove Theorem 1.2. Afterwards, we show that if the links of the complex $X$
are already dense, then the derandomization technique in [BL06] works for high
dimensional expanders, and we can obtain a deterministic construction for
$(k-1)$-bounded $k$-dimensional high dimensional expanders, proving Theorem
1.3.

###  1.4 Understanding Vertex vs. Edge Degree in Bounded-Degree Constructions

We can use Theorem 1.2 to diversifying links in other existing bounded degree
constructions, and thus gain more understanding on how possible high
dimesional expanders may look like. For simplicity, let us stick to the
$2$-dimensional case, and consider the question _how small could $d_{1}$ be
given $d_{0}$ in a $(d_{0},d_{1})$-regular high dimensional expander?_

Let us consider the behavior of $d_{0}$ and $d_{1}$ in the known bounded
degree constructions [Bal00, CSŻ03, Li04, LSV05, KO18, FI20, Dik22, DDL24,
BLM24]. In all the above, $d_{0}$ grows to infinity as $\lambda$ goes to $0$,
and $d_{1}=\operatorname{poly}(d_{0})$222Technically most of the constructions
above are not _regular_ , only bounded degree, so $d_{0}$ and $d_{1}$ should
be average values, but we ignore this point for the sake of presentation.. In
other words, the links themselves are “locally” dense. A natural question to
ask is whether the lower bound of $d_{1}\geqslant d_{0}^{\Omega(1)}$ is
necessary for bounded degree constructions. In expander _graphs_ it is well
known that one can increase the size of the graph without increasing the bound
on the degree, but this is not the behavior in the known bounded-degree HDX
constructions.

Theorem 1.3 gives a negative answer to this question in the $2$-dimensional
case, by proving the following.

######  Theorem 1.4.

For every $\lambda>0$ and any sufficiently large $M>0$, there exists an
infinite family of $2$-dimensional $\lambda$-two sided high dimensional
expanders that are
$(d_{0},\exp(\operatorname{poly}(\frac{1}{\lambda})))$-regular, for
$M\leqslant d_{0}\leqslant 2M$.

We stress that $d_{1}=\exp(\operatorname{poly}(\frac{1}{\tilde{\lambda}}))$
depends only on the spectral expansion and not on the number of vertices or
$d_{0}$.

###  1.5 Related Work

##### Bounded degree HDX

As discussed above, all known constructions of bounded degree high dimensional
expanders use algebraic techniques. The first bounded degree high dimensional
expanders for arbitrarily small $\lambda>0$ was by [Bal00]. This was followed
by many other works that aimed to construct the high dimensional equivalent to
Ramanujan graphs [CSŻ03, Li04, LSV05a, LSV05]. All these constructions are
quotients of $\tilde{A}$-type Bruhat Tits buildings. The work by [Dik22] used
this building together with complex lifts to construct other high dimensional
expanders. Recently, high dimensional expanders that come from $\tilde{C}$
Bruhat Tits buildings were also constructed and studied [CL23, DDL24, BLM24].
A second type of constructions come from coset complexes, first studied by
[KO18]. More complexes of this type were constructed by [FI20, OP22].
Interestingly, [LLR19] give a randomized construction of a $(k-1)$-bounded
degree family of $\lambda$-HDXs for arbitrarily small $\lambda>0$. This
construction is based on random Steiner systems and given in the breakthrough
result of [Kee14]. The underlying $(k-1)$-skeletons of the complexes in that
family are complete.

There are other bounded degree constructions [Con19, CTZ20, CLY20, LMY20,
Gol21]. These constructions have various mixing properties, but none of them
are $\lambda$-HDXs for $\lambda\leqslant\frac{1}{2}$ (where $\lambda$ is
normalized between $0$ and $1$). There are other constructions of
$\lambda$-HDXs for arbitrarily small $\lambda$, which are not bounded degree,
but are still non-trivially sparse. These include [Gol23] \- based on
Grassmann posets, and [Liu+23] \- based on random geometric graphs of the
sphere.

Finally, we comment that previous works also considered the possible degrees
$(d_{0},d_{1})$ possible in a high dimensional expanders. The work by [FI20]
used irregular algebraic constructions of bounded degree $\lambda$-HDXs and
‘regularized’ them, thus showing that there exists bounded degree HDXs that
are regular for arbitrarily small $\lambda$. The work by [CLY20] gives a lower
bound on the expansion of the underlying graph of the complex in terms of
$(d_{0},d_{1})$, but this lower bound does not rule out (or construct) such
HDXs with $d_{1}\ll d_{0}$.

##### Graph and HDX lifts

The study of random graph lifting was initiated in [AL02]. Random lifts from
signings of expanders were studied in [BL06] where it was proven that with
high probability they are also expanders. This was extended to larger lifts as
well [Oli09, AG10]. Friedman showed that random lifts of Ramanujan graphs are
nearly Ramanujan [Fri08] (see also [Bor20]). In the seminal paper by [MSS15],
Ramanujan bipartite graphs were constructed by using graph lifts. One can also
define lifts of simplicial complexes. Most known bounded degree high
dimensional expanders in a dual notion of lifts - that is, taking quotients of
an infinite object [Bal00, CSŻ03, Li04, LSV05a, LSV05, KO18], in a way such
that the infinite object is a lift of the complex that is constructed. [Dik22]
studied taking random lifts of simplicial complexes as in [BL06], but the
construction there needed the use of algebraic techniques as well.

###  1.6 Open Questions

##### Combinatorial constructions

As we mention earlier, there is no construction of bounded degree high
dimensional expanders that does not rely on non-trivial algebraic techniques.
As an intermediate step towards such a construction, can one give a
construction of $k$-dimensional simplicial complexes that are $(k-2)$-bounded
degree (or $i$-bounded degree for any $i<k-1$)?

##### Links with other properties

Fix a vertex set $[n]$ and graphs $\left\\{G_{i}\right\\}_{i=1}^{n}$ (one
graph for every vertex $i\in[n]$). It is interesting to understand whether
there exists a graph whose vertex set is $V=[n]$, and such that the
neighborhood of every vertex $i\in V$ is (isomorphic to) $G_{i}$. The
structure of such graphs is an extensive topic of study, especially in the
case where all $G_{i}$’s are equal (see, e.g., [BC75, BB89, Már+03]). One of
the major components in the works [Din+22, PK22] that constructed
asymptotically good locally testable codes and quantum codes, is a
construction of graphs that locally look like a neighborhood of a graph
product, but globally have improved expansion properties.

In this work, we propose a technique that addresses a related problem. Given a
graph $G$ (which is the one skeleton of a regular $2$-dimensional complex
$X$), we find a graph $\widehat{G}$ where every neighborhood in $\widehat{G}$
is a random (or deterministic) $2$-lift of a corresponding neighborhood in
$G$. Is there a technique that allows us to do so for _any_ set of $2$-lifts
of the respective vertex neighborhoods?

##### Other notions of expansion

In this paper we mainly deal with local spectral expansion, but other
definitions of high dimensional expansion also exist. Most notable is the
notion of coboundary expansion defined independently in [LM06] and [Gro10].
This notion is important for many applications of high dimensional expanders
such as code construction [Din+22], topological expansion [Gro10] and property
testing [KL14, GK22, DD23, BM23]. Does a local lift maintain coboundary
expansion? If not, is it maintained in interesting special cases?

####  1.6.1 Organization of This Paper

The necessary preliminaries are given in Section 2. We describe local lifts in
Section 3 and describe some of their basic properties. In Section 4 we show
existence of good local lifts by modifying a Lovász Local Lemma argument by
[BL06]. In Section 5 we prove Theorem 1.2 using the algorithmic Lovász Local
Lemma [MT10] and derive Theorem 1.4. In Section 6 we show that the method of
derandomization in [BL06] could be generalized to our case as well and prove
Theorem 1.3.

##  2 Preliminaries

Unless explicitly stated, all logarithms are with base $2$. The $\ln$ function
is a logarithm with base $e$. We write $A\sqcup B$ to denote a disjoint union
of sets $A,B$. The For $n\geqslant 0$ we write
$[n]=\left\\{0,1,\dots,n\right\\}$. For a square matrix (or equivalently, a
linear operator on a finite vector space), we write $\lVert A\rVert$ to denote
the operator norm.

###  2.1 Graphs

Let $G=(V,E)$ be a graph. For $u,v\in V$ we write $\Gamma(v)$ for the set of
$v$’s neighbors in $G$ and $u\sim v$ if $u$ and $v$ are neighbors. The
_indicator vector_ of a set $S\subseteq V$, denoted by $\mathbb{1}_{S}$, is
$\mathbb{1}_{S}:V\to\left\\{0,1\right\\}$ with $\mathbb{1}_{S}(v)=1\iff v\in
V$. For two sets $S,T\subseteq V$ we write $E_{G}(S,T)$ for the set of edges
in $G$ between $S$ and $T$. The _graph induced by $S$ and $T$_ is
$G^{\prime}=(S\cup T,E_{G}(S,T))$.

For a $d$-regular graph we denote
$\ell_{2}(V)=\left\\{f:V\to\mathbb{R}\right\\}$ endowed with the inner product

$\langle f,g\rangle=\sum_{v\in V}f(v)g(v).$

####  2.1.1 Expander Graphs

Expander graphs are graphs with good connectivity properties. There are many
equivalent ways to define expanders [HLW06]. In this manuscript we focus on
_spectral expansion_.

Let $G=(V,E)$ be a $d$-regular graph. The _random walk matrix_ of $G$ is a
matrix $A\in\mathbb{R}^{V\times V}$ defined by $A(u,v)=\frac{1}{d}$ if
$u\in\Gamma(v)$ and otherwise $0$. Equivalently, it corresponds to the random
walk operator $A:\ell_{2}(V)\to\ell_{2}(V)$ with
$Af(v)=\frac{1}{d}\sum_{u\in\Gamma(v)}f(u)$. We abuse notation and use $A$ for
both the matrix and the random walk operator it represents. We sometimes
denote this operator by $A_{G}$ when $G$ is unclear from the context.

The operator $A$ is self adjoint with respect to the inner product. Therefore,
it has an orthonormal basis of real-valued eigenvectors, where the eigenvalues
are denoted by
$1=\lambda_{1}\geqslant\lambda_{2}\geqslant\cdots\geqslant\lambda_{n}$. We
elaborate and write $\lambda_{i}(G)$ when the graph in question is unclear
from the context. The _spectrum of $G$_ is the spectrum of its random walk
matrix and is denoted by $\mathsf{Spec}(G)$.

######  Definition 2.1 (spectral expander).

For $\lambda\in[0,1]$ we say that $G$ is _$\lambda$ -two sided (resp. one
sided) spectral expander_ (or _expander_ for short) if
$\lambda\geqslant\max\\{\lambda_{2},|\lambda_{n}|\\}$ (resp.
$\lambda\geqslant\lambda_{2}$).

####  2.1.2 Tensor Product

Let $G,H$ be any graphs. The _tensor product_ of $G$ and $H$, denoted by
$G\otimes H$, is the graph with vertices $V(G)\times V(H)$, and edges
$E(G\otimes
H)=\left\\{(a,b)(a^{\prime},b^{\prime})\left|\;\vphantom{(a,b)(a^{\prime},b^{\prime})\left\\{a,a^{\prime}\right\\}\in
E(G)\;\hbox{and}\;\left\\{b,b^{\prime}\right\\}\in
E(H)}\right.\left\\{a,a^{\prime}\right\\}\in
E(G)\;\hbox{and}\;\left\\{b,b^{\prime}\right\\}\in E(H)\right\\}$.

The following fact is well known.

######  Fact 2.2.

Let $G,H$ be graphs. If $H,G$ are $\lambda,\lambda^{\prime}$-two sided
spectral expanders respectively, then $G\otimes H$ is a
$\max\\{\lambda,\lambda^{\prime}\\}$-two sided spectral expander. Moreover, if
$H$ is a $\lambda$-two sided spectral expander and $G$ is a
_$\lambda^{\prime}$ -one sided_ spectral expander, then $G\otimes H$ is a
$\max\\{\lambda,\lambda^{\prime}\\}$-one sided spectral expander.

###  2.2 Graph Lifts

Graph lifts are an important notion, studied first by [AL02, Ami+01] (although
the notion of lifts themselves is a classical notion in algebraic topology
known for about a century).

######  Definition 2.3 (lift).

For finite, connected and simple graphs $G$ and $\widehat{G}$, a _lift_ (also
known as a covering map) $\phi:\widehat{G}\to G$ is a graph homomorphism with
the property that for all $\hat{v}\in V(\widehat{G})$, $\phi$ maps the
neighborhood of $\hat{v}$ in $\widehat{G}$ onto the neighborhood of
$\phi(\hat{v})$ in $G$. Finally, we say that $\widehat{G}$ is an _$\ell$ -lift
of $G$_ if there exists an $\ell$-to-$1$ covering map $\phi:\widehat{G}\to G$.

One way to construct a $2$-lift is to use a signing function on the edges as
follows.

######  Definition 2.4 (Function induced lift).

Let $G=(V,E)$ be a graph and let $f:E\to\left\\{\pm 1\right\\}$ be a signing.
The _$f$ -induced lift_ $\widehat{G}=\widehat{G}^{f}$ is the graph whose
vertices are

$\widehat{V}=V\times\left\\{\pm
1\right\\}=\left\\{v^{j}\left|\;\vphantom{v^{j}v\in V,j\in\left\\{\pm
1\right\\}}\right.v\in V,j\in\left\\{\pm 1\right\\}\right\\}$

and whose edges are

$\widehat{E}=\left\\{\left\\{v^{j},u^{i}\right\\}\left|\;\vphantom{\left\\{v^{j},u^{i}\right\\}\left\\{v,u\right\\}\in
E,ij=f(\left\\{u,v\right\\})}\right.\left\\{v,u\right\\}\in
E,ij=f(\left\\{u,v\right\\})\right\\}.$

The lift map is $\phi(v^{j})=v$.

It is elementary to prove this construction is indeed a lift, so we omit this
proof. It is also easy to show that any $2$-lift is an induced lift for some
signing $f:V(G)\to\left\\{\pm 1\right\\}$. See [Sur84] for a more general
statement and proof.

In Section 3 we generalize the notion of graph lifts to _local lifts_ of
simplicial complexes.

####  2.2.1 Signing Functions and Lift Expansion

Fix a graph $G$ and a signing $f:E(G)\to\left\\{\pm 1\right\\}$. In this
subsection, we characterize the eigenvalues of an $f$-induced lift. For this,
we need to define the $f$-signing of an adjacency operator. For a $d$-regular
graph the $f$-signing of the adjacency operator is the matrix
$A^{f}(u,v)=f(u,v)\cdot A(u,v)$ for $\left\\{u,v\right\\}\in E$ and
$A^{f}(u,v)=0$ if $\left\\{u,v\right\\}\notin E$.

This signing matrix is closely related to the random walk operator of the
lift. In particular, the following is by now classical.

######  Lemma 2.5.

Let $G$ be a $d$-regular graph and let $\widehat{G}$ be an $f$-induced
$2$-lift. Then the eigenvalues of $A_{\widehat{G}}$ are the union (with
multiplicities) of the eigenvalues of $A$ and those of $A^{f}$. In particular,
if $\lVert A^{f}\rVert\leqslant\lambda$ and $G$ is a $\lambda^{\prime}$-two
sided (resp. one sided) spectral expander, then $\widehat{G}$ is a
$\max\left\\{\lambda,\lambda^{\prime}\right\\}$-two sided (resp. one sided)
spectral expander.

Using this lemma, [BL06] gave a criterion for the expansion of the lift graph.

######  Lemma 2.6 ([BL06, Lemma 3.3]).

Let $G,f$ and $A^{f}$ be as above and assume that $G$ is a $\lambda$-two sided
(resp. one sided) spectral expander with no self loops. Assume that for any
pair of disjoint $S,T\subseteq V(G)$

$\left\lvert\left\langle\mathbb{1}_{S},A^{f}\mathbb{1}_{T}\right\rangle\right\rvert\leqslant\alpha\sqrt{|S||T|},$

then $\widehat{G}^{f}$ is a $\lambda^{\prime}$-two sided (resp. one-sided)
spectral expander where
$\lambda^{\prime}=\max\left\\{\lambda,O\left(\alpha\left(1+\log\frac{1}{\alpha}\right)\right)\right\\}$.

We note that there is a nice formula for this inner product, which is

$\left\langle\mathbb{1}_{S},A^{f}\mathbb{1}_{T}\right\rangle=\frac{1}{d}\sum_{(v,u):\left\\{v,u\right\\}\in
E(G)}f(u,v)\mathbb{1}_{S}(v)\mathbb{1}_{T}(u).$

###  2.3 High Dimensional Expanders

######  Definition 2.7 (simplicial complex).

A _$k$ -dimensional simplicial complex_ is a finite hypergraph $X$ that is
downwards closed to containment. That is, if $\tau\in X$ and
$\sigma\subseteq\tau$ then $\sigma\in X$.

We write $X=X(-1)\sqcup X(0)\sqcup X(1)\sqcup\cdots\sqcup X(k)$, where
$X(\ell)=\left\\{\sigma\in X\left|\;\vphantom{\sigma\in
X|\sigma|=\ell+1}\right.|\sigma|=\ell+1\right\\}$ (here
$X(-1)=\left\\{\emptyset\right\\}$ is mainly a formality) and the maximal size
of a set $\sigma\in X$ is $k+1$. We call elements $\sigma\in X(\ell)$ _$\ell$
-faces_, and in this case we say that $X$ is $k$-dimensional. In this paper we
will always assume the simplicial complex in question is _pure_ , that is,
that every $\sigma\in X(\ell)$ contained in some $\tau\in X(k)$. In addition,
we assume it has no self-loops or multifaces. Namely, every vertex appears at
most once in each face and any face appears at most once in $X$.

##### Degrees and regularity

The degree of a face $\sigma\in X(i)$ is $d(\sigma)=\lvert\left\\{\tau\in
X(i+1)\left|\;\vphantom{\tau\in
X(i+1)\tau\supseteq\sigma}\right.\tau\supseteq\sigma\right\\}\rvert$. We say
that a family of simplicial complexes $\left\\{X_{i}\right\\}_{i=0}^{\infty}$
is _$j$ -bounded degree_ if there is an integer $M>0$ so that for all $X_{i}$
and all $\sigma\in X_{i}(j)$, $d(\sigma)\leqslant M$. If the family is
$0$-bounded degree, we sometimes just say bounded degree (without the zero).

######  Definition 2.8 (hyper-regularity).

Let $d_{0}\geqslant d_{1}\geqslant\cdots\geqslant d_{k-1}$ be positive
integers. A $k$-dimensional simplicial complex $X$ is
_$(d_{0},d_{1},\ldots,d_{k-1})$ -regular_ if for any $i\in\\{0,\ldots,k-1\\}$
and any $i$-face $\sigma$, $d(\sigma)=d_{i}$.

We say that $X$ is regular if there exists such a tuple so that $X$ is
$(d_{0},d_{1},\ldots,d_{k-1})$-regular. In this case we denote by
$d_{i}(X)=d_{i}$.

##### Skeletons and links

The _$j$ -skeleton_ of a simplicial complex $X$ is the simplicial complex
obtained by taking all the $i$-faces of $X$, for all $i\leqslant j$. The
$1$-skeleton of a complex is also called an _underlying graph_.

A link is a generalization of a graph neighborhood.

######  Definition 2.9 (link).

For a $k$-dimensional simplicial complex $X$ and a face $\sigma\in X$, the
_link of $\sigma$_ is the $(k-1-|\sigma|)$-dimensional simplicial complex

$X_{\sigma}=\left\\{\tau\setminus\sigma\left|\;\vphantom{\tau\setminus\sigma\tau\in
X,\tau\supset\sigma}\right.\tau\in X,\tau\supset\sigma\right\\}.$

For $\ell\leqslant k-2$ and $\sigma\in X(\ell)$ we denote by $A_{\sigma}$ the
random walk operator of the $1$-skeleton of $X_{\sigma}$. We often abuse of
notation and for a face $\sigma=\\{v_{0},\ldots,v_{\ell}\\}\in X(\ell)$ write
$\sigma=v_{0}\ldots v_{\ell}$.

Natural analogues of expander graphs to higher dimensions are simplicial
complexes where the neighborhoods of the faces are themselves expander graphs.
See Section 1 for more context on this important definition.

######  Definition 2.10 ($\lambda$-high dimensional expander).

Let $\lambda\in[0,1]$. A $k$-dimensional simplicial complex $X$ is a
_$\lambda$ -two sided (resp. one sided) high dimensional expander_ if for all
$i\leqslant k-2$ and all $\sigma\in X(i)$, the 1-skeleton of $X_{\sigma}$ is a
$\lambda$-two sided (resp. one sided) spectral expander.

###  2.4 The Lovász Local Lemma

The Lovász Local Lemma is a classical result in the probabilistic method.

######  Lemma 2.11 (Lovász Local Lemma [EL75]).

Let $\mathfrak{B}=\\{B_{1},\ldots,B_{n}\\}$ be a finite set of events in some
arbitrary probability space. The _dependency graph of $\mathfrak{B}$_ is a
digraph $G_{\mathfrak{B}}=(\mathfrak{B},E)$ so that any event
$B_{i}\in\mathfrak{B}$ is mutually independent of all the events
$\mathfrak{B}\setminus\Gamma(B_{i})$, where $\Gamma(B_{i})$ is the
neighborhood of $B_{i}$ in $G_{\mathfrak{B}}$.

If there exists a real function $\rho:\mathfrak{B}\to[0,1)$ so that

$\operatorname*{\mathbb{P}}\\!\left[B_{i}\right]\leqslant\rho(B_{i})\prod_{B_{j}\sim
B_{i}}\left(1-\rho(B_{j})\right)$ (2.1)

for any $B_{i}\in\mathfrak{B}$, then none of the events $B_{i}$ occur with
strictly positive probability.

This lemma also has an algorithmic version, first given in the seminal work of
[MT10]. We give below a slightly less general version than the one in [MT10].

######  Lemma 2.12 ([MT10]).

Let $\Omega$ be a finite set and let $\mathfrak{P}=(P_{1},P_{2},\dots,P_{m})$
be a tuple of independent random variables supported on $\Omega^{m}$. Let
$\mathfrak{B}=\left\\{B_{1},B_{2},\dots,B_{n}\right\\}$ be a finite set of
events in the sigma algebra of $\mathfrak{P}$. Let the dependency graph and
the assignment $\rho:\mathfrak{B}\to[0,1)$ be as in Lemma 2.11. Then there
exists a randomized algorithm that finds an assignment $p\in\Omega^{m}$ such
that $p\notin\bigcup_{i=1}^{n}B_{i}$. If one can verify whether $B_{i}$ holds
in time $t$, then the randomized algorithm runs in
$tn\sum_{i=1}^{n}\frac{\rho(B_{i})}{1-\rho(B_{i})}$ expected time.

The algorithm described in this lemma is simple. The algorithm starts with
randomly sampling some $p\in\Omega^{m}$. While there exists some $B_{i}$ such
that $p\in B_{i}$, the algorithm takes an arbitrary such $B_{i}$, and
resamples all the coordinates $P_{j}$ that $B_{i}$ depends upon. Of course, if
the algorithm halts, then $p\notin\bigcup_{i=1}^{n}B_{i}$. The paper [MT10]
shows that the expected number of times an event $B_{i}$ is resampled is at
most $\frac{\rho(B_{i})}{1-\rho(B_{i})}$ which explains the runtime of this
algorithm.

##  3 Local lifts

This section presents our basic construction, the _local lift_ of a complex.
We will define this construction formally and describe some of its properties.

######  Construction 3.1 (Local Lift).

Let $X$ be a $k$-dimensional simplicial complex and let $f:X(k)\to\\{\pm
1\\}$. The _$f$ -local lift_ of $X$ denoted by $\widehat{X}=\widehat{X}^{f}$,
is the following $k$-dimensional simplicial complex:

  * –

$\widehat{X}(0)=X(0)\times\left\\{\pm 1\right\\}$ and we denote the vertices
by $\widehat{X}(0)=\left\\{v^{j}\left|\;\vphantom{v^{j}v\in
X(0),j\in\left\\{\pm 1\right\\}}\right.v\in X(0),j\in\left\\{\pm
1\right\\}\right\\}$.

  * –

For any $1\leqslant\ell\leqslant k-1$,

$\widehat{X}(\ell)=\left\\{\,\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\ldots,v_{\ell}^{j_{\ell}}\\}\;\middle|\;\\{v_{0},v_{1}\ldots,v_{\ell}\\}\in
X(\ell),\ j_{0},\ldots,j_{\ell}\in\\{\pm 1\\}\,\right\\}.$

  * –

Finally, $\widehat{X}(k)$ is the set of all faces
$\sigma=\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{d}^{j_{k}}\right\\}$ so
that the face without the signs is
$\left\\{v_{0},v_{1},\dots,v_{k}\right\\}\in X(k)$, and the product of the
$j_{i}$’s are equal to $f(\sigma)$. Namely,

$\widehat{X}(k)=\left\\{\,\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\ldots,v_{k}^{j_{k}}\right\\}\;\middle|\;\\{v_{0},v_{1},\ldots,v_{k}\\}\in
X(k),\;\;f(\\{v_{0},v_{1},\ldots,v_{k}\\})=\prod_{i=0}^{k}j_{i}\,\right\\}.$

One can already see that the $(k-1)$-skeleton of $\widehat{X}$ doesn’t depend
on $X$ and is just some inflation of the original complex. The dependence on
$f$ is only in the top-level faces. Thus, in particular, $\widehat{X}$ is not
a lift of (the underlying graph) of $X$, except when $k=1$. However, the links
of $(k-2)$-faces in $\widehat{X}$ are lifts of links in $X$, which is why we
named this complex a local lift. We will see this in the next subsection.

###  3.1 Local Properties of Local Lifts

For the rest of this subsection, we fix $X$ to be a $k$-dimensional pure
simplicial complex, $f:X(k)\to\\{\pm 1\\}$ to be a signing function, and
$\widehat{X}$ to be the $f$-local lift of $X$. We also need the following
three pieces of notation:

  1. 1.

Let $\pi:\widehat{X}(0)\to X(0)$ be the projection map $\pi(v^{j})=v$, and we
extend it to higher dimensional faces as well by
$\pi(\left\\{v_{0}^{j_{0}},v_{1}^{j_{1}},\dots,v_{i}^{j_{i}}\right\\})=\left\\{v_{0},v_{1},\dots,v_{i}\right\\}$.

  2. 2.

Let $\operatorname{sign}:\widehat{X}\to\\{\pm 1\\}$ be
$\operatorname{sign}(\hat{\sigma})\to\prod_{v^{j}\in\hat{\sigma}}j$.

  3. 3.

For any $\hat{\sigma}\in\widehat{X}(k-2)$ with $\sigma=\pi(\hat{\sigma})$ we
denote by $f_{\sigma}:X_{\sigma}(1)\to\left\\{\pm 1\right\\}$ the function
$f_{\sigma}(e)=f(\sigma\sqcup e)$ and by
$f_{\hat{\sigma}}:X_{\sigma}(1)\to\left\\{\pm 1\right\\}$ the function
$f_{\hat{\sigma}}(e)=\operatorname{sign}(\hat{\sigma})\cdot f_{\sigma}(e)$.

The first observation is that the degrees of $\widehat{X}$ are twice the
degrees of $X$, except for $d_{k-1}$, which stays the same.

######  Observation 3.2.

If $X$ is $(d_{0},\ldots,d_{k-1})$-regular then $\widehat{X}$ is
$(2d_{0},2d_{1}\ldots,2d_{k-2},d_{k-1})$-regular. ∎

It is a direct calculation, so we have omitted its proof. We just comment that
the reason that $d_{k-1}$ remains the same is that for every
$\hat{\sigma}\in\widehat{X}(k-1)$ and $v\in X_{\pi(\hat{\sigma})}(0)$ there is
exactly one $j\in\left\\{\pm 1\right\\}$ such that
$\hat{\sigma}\cup\left\\{v^{j}\right\\}\in\widehat{X}(k)$. Therefore,
$d_{k-1}(X)=|X_{\pi(\hat{\sigma})}(0)|=|\widehat{X}_{\hat{\sigma}}(0)|=d_{k-1}(\widehat{X})$.
The next lemma gives a complete description of the links of $\widehat{X}$.

######  Lemma 3.3 (on the structure of the links).

Let $\hat{\sigma}\in\widehat{X}$ and denote by $\sigma=\pi(\hat{\sigma})$.

  1. 1.

If $\mathrm{dim}(\hat{\sigma})<k-2$, then the 1-skeleton of
$\widehat{X}_{\hat{\sigma}}$ (the $\hat{\sigma}$-link of $\widehat{X}$), is
isomorphic to the 1-skeleton of $X_{\sigma}$ tensored with the complete graph
on two vertices with self loops333Note that this is also true for the link of
$\sigma=\emptyset$, i.e. $\widehat{X}$ itself..

  2. 2.

If $\mathrm{dim}(\hat{\sigma})=k-2$, then $\widehat{X}_{\hat{\sigma}}$ is
isomorphic to a lift of $X_{\sigma}$ induced by $f_{\hat{\sigma}}$.

###### Proof.

The first item directly follows from the definition of a tensor product. For
the second item, suppose $\mathrm{dim}(\hat{\sigma})=k-2$. Both the vertices
of $\widehat{X}_{\hat{\sigma}}$ and of the $f_{\hat{\sigma}}$-induced lift of
$X_{\sigma}$ are $X_{\sigma}(0)\times\left\\{\pm 1\right\\}$. As for the
edges, $\left\\{u^{i},v^{j}\right\\}\in\widehat{X}_{\hat{\sigma}}(1)$ if and
only if $\left\\{u,v\right\\}\in X_{\sigma}(1)$ and
$ij\cdot\operatorname{sign}(\hat{\sigma})=f(\sigma\sqcup\left\\{u,v\right\\})$
(or equivalently $ij=f_{\hat{\sigma}}(\left\\{u,v\right\\})$). This is
precisely the relation that defines edges in the $f_{\hat{\sigma}}$-induced
lift of $X_{\sigma}$. ∎

The following corollary that bounds the spectrum of the links is direct.

######  Corollary 3.4.

Let $\hat{\sigma}\in\widehat{X}$ and denote $\sigma=\pi(\hat{\sigma})$.

  1. 1.

If $\mathrm{dim}(\hat{\sigma})<k-2$ then
$\lambda(\widehat{X}_{\hat{\sigma}})=\lambda(X_{\sigma})$.

  2. 2.

If $\mathrm{dim}(\hat{\sigma})=k-2$ then
$\mathsf{Spec}(\widehat{X}_{\hat{\sigma}})=\mathsf{Spec}(A_{\sigma})\cup\mathsf{Spec}(A^{f_{\hat{\sigma}}}_{\sigma})$,
where $A_{\sigma}$ is the normalized adjacency matrices of $X_{\sigma}$ and
$A_{\sigma}^{f_{\hat{\sigma}}}$ is its signed normalized adjacency matrix with
respect to $f_{\hat{\sigma}}$.

###### Proof.

The first item follows from Fact 2.2. The second item follows from Lemma 2.5
and the fact that the link is the $f_{\hat{\sigma}}$-induced lift of
$X_{\sigma}$ as we saw in Lemma 3.3. ∎

##  4 Families of HDXs via Random Local Lifts

This section is dedicated to existential proofs of high dimensional expanders
based on our local lifts from Construction 3.1. We start by stating the main
theorem of this section which asserts that given an arbitrary HDX $X$, there
exists a family of HDXs with parameters comparable to those of $X$ so that any
member of the family is a local lift of the former. Formally,

######  Theorem 4.1.

Let $X_{0}$ be a $(d_{0},d_{1},\dots,d_{k-1})$-regular $\lambda$-two sided
(resp. one sided) HDX over $n$ vertices, for $\lambda\in[0,1]$. Then there
exists a family of
$\max\left\\{\lambda,O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)\right\\}$-two
sided (resp. one sided) high dimensional expanders
$\\{X_{i}\\}_{i=0}^{\infty}$ so that $X_{i}$ is a
$(2^{i}d_{0},\ldots,2^{i}d_{k-2},d_{k-1})$-regular complex over $2^{i}n$
vertices and $X_{i+1}$ is a local lift of $X_{i}$.

The proof of Theorem 4.1 is based on proving the single-step version of it,
given in Theorem 4.2, and applying it iteratively.

######  Theorem 4.2.

Let $\lambda\in[0,1]$. For any $k$-dimensional,
$(d_{0},\ldots,d_{k-1})$-regular, $\lambda$-two sided (resp. one sided) high
dimensional expander $X$ over $n$ vertices, there exists a signing
$f:X(k)\to\\{\pm 1\\}$ so that $\widehat{X}$ is a
$\max\left\\{\lambda,O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)\right\\}$-two
sided (resp. one sided) high dimensional expander with regularity
$(2d_{0},\ldots,2d_{k-2},d_{k-1})$ and $2n$ vertices.

We start by proving Theorem 4.1 given Theorem 4.2. The proof of Theorem 4.2 is
more involved and is provided in the remainder of this section.

###### Proof of Theorem 4.1 assuming Theorem 4.2.

Let $X_{0}$ as specified in Theorem 4.1 and denote
$\lambda^{\prime}\vcentcolon=\max\left\\{\lambda,O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)\right\\}$.
The proof is by induction on $i$. Clearly $X_{0}$ holds the requirements.

For the induction step, let $X_{i}$ be a
$(2^{i}d_{0},\ldots,2^{i}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two
sided (resp. one sided) HDX with $2^{i}n$ vertices received in the $i$-th step
of the process. By Theorem 4.2, there exists a singing function
$f_{i}:X_{i}(k)\to\\{\pm 1\\}$ so that the $f_{i}$-local lift of $X_{i}$
(denoted by $\widehat{X_{i}}$) is a
$(2^{i+1}d_{0},\ldots,2^{i+1}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two
sided (resp. one sided) HDX over $2^{i+1}n$ vertices. Setting
$X_{i+1}\vcentcolon=\widehat{X_{i}}$ concludes the proof. ∎

###  4.1 Proof Outline of Theorem 4.2

The proof of Theorem 4.2 is based on Lovász Local Lemma [EL75] and Lemma 2.6,
and closely follows the lines of the existential proof in [BL06].

Recall that one approach for proving a given $k$-dimensional simplicial
complex is $\lambda$-HDX, is considering all of its $\ell$-links for
$\ell\leqslant k-2$ and bound the spectrum of each of their $1$-skeletons by
$\lambda$. By Corollary 3.4, the only links one should be concerned with are
those obtained by $(k-2)$-faces, as all other faces inherent the expansion
from the initial HDX. In addition, by the same corollary, it’s enough to
analyze the spectra of the signed random walk matrices of the $(k-2)$-links of
$X$, with respect to the signing induced on them as defined in Lemma 3.3.
Indeed, doing so is the most technical part of the proof and follows by the
next lemma combined with Lemma 2.6:

######  Lemma 4.3.

For any $k$-dimensional pure $(d_{0},\ldots,d_{k-1})$-regular simplicial
complex $X$ over $n$ vertices, there exists a signing function
$f:X(k)\to\\{\pm 1\\}$ such that for any $(k-2)$-face
$\hat{\sigma}\in\widehat{X}$ and any disjoint subsets of vertices
$S,T\subseteq X_{\sigma}(0)$ for $\sigma=\pi(\hat{\sigma})$,

$\lvert\langle\mathbb{1}_{S},A^{f_{\hat{\sigma}}}_{\sigma}\mathbb{1}_{T}\rangle\rvert\leqslant
10\sqrt{\frac{k^{2}\log d_{k-1}}{d_{k-1}}|S||T|}$ (4.1)

where $f_{\hat{\sigma}}$ is the signing on $X_{\sigma}$’s edges induced by $f$
as defined in Section 3.1.

By the $(d_{0},\ldots,d_{k-1})$-regularity of $X$, $X_{\sigma}$ is a
$d_{k-1}$-regular graph over $d_{k-2}$-vertices. Furthermore, since any
signing over the $k$-faces induces a signing function on the edges of any
$(k-2)$-link, our goal is to find a single signing function $f$ such that
these lifts of all the links of the $(k-2)$-dimensional faces expand.

The proof of Lemma 4.3 is by the Lovász Local Lemma Lemma 2.11. We define the
set of “bad” events $\mathfrak{B}=\\{B^{S,T}_{\sigma}\\}$. The event
$B_{\sigma}^{S,T}$ is that (4.1) doesn’t hold for a fixed $\sigma\in X(k-2)$
and fixed disjoint sets $S,T\subseteq X_{\sigma}(0)$. In [BL06], similar bad
events were considered, but only the sets $S,T$ needed to be specified. The
main difference between our proof and theirs is that we need to take care of
the dependencies between events corresponding to different $(k-2)$-faces
$\sigma,\sigma^{\prime}$.

To apply the lemma and deduce Lemma 4.3, one needs to understand and analyze
the dependency relation of the events in $\mathfrak{B}$.

##### On the dependency of bad events in $\mathfrak{B}$

Fix $\hat{\sigma}\in\widehat{X}(k-2)$ and disjoint $S,T\subseteq
X_{\sigma}(0)$ for $\sigma=\pi(\hat{\sigma})$, and define
$F(\sigma,S,T)\subseteq X(k)$ to be the set of all $k$-faces of $X$ so that
$\sigma\subseteq\tau$ and $\tau\setminus\sigma$ is an edge in the graph
induces by $S\sqcup T$ on $X_{\sigma}$. Recall that
$\operatorname{sign}:\widehat{X}\to\\{\pm 1\\}$ is defined by
$\operatorname{sign}(\hat{\sigma})=\prod_{v^{j}\in\hat{\sigma}}j$, and note
that

$\displaystyle
d_{k-1}\langle\mathbb{1}_{S},A^{f_{\hat{\sigma}}}_{\sigma}\mathbb{1}_{T}\rangle$
$\displaystyle=\\!\\!\\!\\!\\!\\!\sum_{\begin{subarray}{c}uv\in
X_{\sigma}(1)\\\ \text{s.t. }u\in S,v\in
T\end{subarray}}\\!f_{\hat{\sigma}}(uv)=\operatorname{sign}(\hat{\sigma})\\!\\!\\!\sum_{\begin{subarray}{c}uv\in
X_{\sigma}(1)\\\ \text{s.t. }u\in S,v\in T\end{subarray}}\\!f(\sigma\sqcup
uv)=\operatorname{sign}(\hat{\sigma})\\!\\!\\!\sum_{\tau\in
F(\sigma,S,T)}\\!\\!\\!\\!f(\tau).$

Since the signs $f$ assigns to the $k$-faces are chosen independently, if the
event $B_{\sigma}^{S,T}$ is _not_ mutually independent of a subset
$\mathfrak{A}\subseteq\mathfrak{B}$, there must exists some event
$B_{\sigma^{\prime}}^{S^{\prime},T^{\prime}}\in\mathfrak{A}$ for which
$F(\sigma,S,T)\cap F(\sigma^{\prime},S^{\prime},T^{\prime})$ is not empty.

Towards using the Lovász Local Lemma, we need to bound the probability of the
event $B_{\sigma}^{S,T}$ as well as the number of neighbors it has in the
dependency graph considered in the Local Lemma. The bound on the probability
follows directly from the arguments in [BL06], but bounding the number of
neighbors each event is more involved. In contrast to the expander graph case
considered in [BL06] (where the “bad” events only depend on $S$ and $T$), in
simplicial complexes events corresponding to different faces
$\sigma,\sigma^{\prime}$ (and therefore to different links) can depend on one
another as long as they have a common $k$-face in $F(\sigma,S,T)\cap
F(\sigma^{\prime},S^{\prime},T^{\prime})$. A naive count of the number of such
$k$-faces won’t suffice, and would lead the bound in (4.1) to scale with
$d_{k-2}$. Therefore, we need to carefully characterize when exactly
$F(\sigma,S,T)$ and $F(\sigma^{\prime},S^{\prime},T^{\prime})$ intersect.

The first case where dependency can occur is when $\sigma=\sigma^{\prime}$. In
this case, we are in the same setting as in [BL06], which observed that there
must be an edge in the subgraph induced by $S\cup T$ as well as in the one
induced by $S^{\prime}\cup T^{\prime}$ for a dependency to happen.

In the second case, which is new to our proof, $\sigma\neq\sigma^{\prime}$
meaning that each of the events considers a different graph. In this case, we
observe that this implies both that there is a $k$-face $\tau$ containing both
$\sigma,\sigma^{\prime}$ and that either there exist vertices
$v\in\sigma\cap(S^{\prime}\sqcup T^{\prime})$ and $s\in S\sqcup T$ so that
$\tau\setminus\sigma^{\prime}=\\{v,s\\}$, or that
$\tau\setminus\sigma^{\prime}\subseteq\sigma$. As we show below, this
characterization is useful to bound the number of possible events that are
dependent on a certain $B_{\sigma}^{S,T}$. The following claim gives this
characterization formally.

######  Claim 4.1.1.

Let an event $B^{S,T}_{\sigma}\in\mathfrak{B}$ and some subset
$\mathfrak{A}\subseteq\mathfrak{B}$. If

  * –

for any $B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\in\mathfrak{A}$ with
$\sigma=\sigma^{\prime}$ there is no edge lying in both $E_{X_{\sigma}}(S,T)$
and $E_{X_{\sigma}}(S^{\prime},T^{\prime})$, and

  * –

for any $B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\in\mathfrak{A}$ with
$\sigma\neq\sigma^{\prime}$ there is no $k$-face $\tau\in X$ containing both
$\sigma$ and $\sigma^{\prime}$, so that $\tau\setminus\sigma$ and
$\tau\setminus\sigma^{\prime}$ are edges in $E_{X_{\sigma}}(S,T)$ and
$E_{X_{\sigma^{\prime}}}(S^{\prime},T^{\prime})$ respectively,

then $B^{S,T}_{\sigma}$ is mutually independent of $\mathfrak{A}$.

All left to conclude the proof of Lemma 4.3 is carefully counting the number
of events that fulfill one of the claim conditions and provide a real function
that bounds the probability of each event as in (2.1). We leave the details
for the formal proof, which is given in the next section.

###  4.2 Proving Lemma 4.3

This subsection is dedicated to the proof of Lemma 4.3 together with the
subclaims it requires. We start by setting notations and highlighting features
that will be needed for the proof.

##### Notations

We say that sets $S,T\subseteq X_{\sigma}(0)$ _induce a connected subgraph_ if
the subgraph obtained by projecting $X_{\sigma}$ on $S\cup T$ is connected. In
addition, we write $E_{X_{\sigma}}(S,T)$ to indicate the set of edges between
$S$ and $T$ in $X_{\sigma}$. For $\hat{\sigma}\in\widehat{X}(k-2)$, we denote
$\sigma=\pi(\hat{\sigma})$. When the face $\hat{\sigma}$ being considered is
clear from the context we abbreviate and write $f$ for $f_{\hat{\sigma}}$.

In addition, we rely on the following observation:

######  Observation 4.4.

If a signing $f:X(k)\to\\{\pm 1\\}$ independently assigns a uniform sign to
each $k$-face, then for any $\hat{\sigma}\in\widehat{X}(k-2)$,
$f_{\hat{\sigma}}$ independently assigns a uniform sign to each edge in
$X_{\sigma}$.

###### Proof.

Let $\hat{\sigma}\in\widehat{X}(k-2)$ and let $e\neq e^{\prime}\in
X_{\sigma}(1)$. Then for any $j,j^{\prime}\in\\{\pm 1\\}$

$\displaystyle\operatorname*{\mathbb{P}}\\!\left[f_{\hat{\sigma}}(e)=j\wedge
f_{\hat{\sigma}}(e^{\prime})=j^{\prime}\right]$
$\displaystyle=\operatorname*{\mathbb{P}}\\!\left[\operatorname{sign}(\hat{\sigma})\cdot
f(\sigma\sqcup e)=j\wedge\operatorname{sign}(\hat{\sigma})\cdot f(\sigma\sqcup
e^{\prime})=j^{\prime}\right]$
$\displaystyle=\operatorname*{\mathbb{P}}\\!\left[\operatorname{sign}(\hat{\sigma})\cdot
f(s\sqcup
e)=j\right]\cdot\operatorname*{\mathbb{P}}\\!\left[\operatorname{sign}(\hat{\sigma})\cdot
f(\sigma\sqcup e^{\prime})=j^{\prime}\right]=\frac{1}{4}.$

∎

In addition, as in [BL06], we can restrict the proof to consider only a pair
of sets inducing connected subgraphs and deduce the result to any pair of
sets. In addition, we can assume that $d$ is as large as $996$ as it is always
the case that
$\left\langle\mathbb{1}_{S},A_{\sigma}^{f}\mathbb{1}_{T}\right\rangle\leqslant\sqrt{|S||T|}$
and $1\leqslant 10\sqrt{\frac{k^{2}\log d_{k-1}}{d_{k-1}}}$ for
$d_{k-1}\in[1,996]$.

We are now ready to prove Lemma 4.3.

###### Proof of Lemma 4.3.

We set $f$ to be a randomized signing of $X(k)$ by setting a uniform and
independent sign from $\\{\pm 1\\}$ to any $k$-face. Fix some face
$\hat{\sigma}\in\widehat{X}(k-2)$ with $\pi(\hat{\sigma})=\sigma$, and
disjoint sets $S,T\subseteq X_{\sigma}(0)$. Denote the “bad” event in which
the claim does not hold for our fixed face and sets by $B_{\sigma}^{S,T}$.
That is,

$\operatorname*{\mathbb{P}}\\!\left[B_{\sigma}^{S,T}\right]=\operatorname*{\mathbb{P}}\\!\left[\lvert\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle\rvert>10\sqrt{\frac{k^{2}\log
d_{k-1}}{d_{k-1}}|S||T|}\right].$

Fix for a moment some edge $uv\in X_{\sigma}(1)$, and consider the $(u,v)$-th
entry of $A^{f}_{\sigma}$. By Definition 2.4,
$A^{f}_{\sigma}(u,v)=\frac{1}{d_{k-1}}f_{\hat{\sigma}}(uv)$, which, per
Observation 4.4, distributed uniformly in $\\{\pm 1\\}$ and is independent of
all other edges signs. In addition, since

$\displaystyle\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle=\frac{1}{d_{k-1}}\sum_{\begin{subarray}{c}uv\in
E_{X_{\sigma}}(S,T)\end{subarray}}f_{\hat{\sigma}}(uv),$

$\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle$ is a sum of
independent uniform random variables over $\\{\pm 1\\}$, implying that

$\operatorname*{\mathbb{E}}_{f}\left[\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle\right]=\frac{1}{d_{k-1}}\sum_{\begin{subarray}{c}uv\in
E_{X_{\sigma}}(S,T)\end{subarray}}\operatorname*{\mathbb{E}}_{f}\left[f_{\hat{\sigma}}(uv)\right]=0.$

Hence, by Hoeffding’s inequality,

$\displaystyle\operatorname*{\mathbb{P}}\\!\left[B^{S,T}_{\sigma}\right]=\operatorname*{\mathbb{P}}\\!\left[\left\lvert\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle\right\rvert>10\sqrt{\frac{k^{2}\log
d_{k-1}}{d_{k-1}}|S||T|}\right]\leqslant 2\exp\left(-\frac{2\cdot
100\frac{k^{2}\ln d_{k-1}}{d_{k-1}}|S||T|}{\underset{\begin{subarray}{c}uv\in
E_{X_{\sigma}}(S,T)\end{subarray}}{\sum}\\!\\!\left(\frac{1}{d_{k-1}}-(-\frac{1}{d_{k-1}})\right)^{2}}\right).$
(4.2)

Assuming w.l.o.g. that $|S|\geqslant|T|$ we get

$\displaystyle\frac{200\frac{k^{2}\ln
d_{k-1}}{d_{k-1}}|S||T|}{\underset{\begin{subarray}{c}uv\in
E_{X_{\sigma}}(S,T)\end{subarray}}{\sum}\\!\\!\left(\frac{1}{d_{k-1}}-(-\frac{1}{d_{k-1}})\right)^{2}}$
$\displaystyle=\frac{200k^{2}d_{k-1}(\ln
d_{k-1})|S||T|}{4|E_{X_{\sigma}}(S,T)|}$
$\displaystyle\geqslant\frac{50k^{2}d_{k-1}(\ln d_{k-1})|S||T|}{d_{k-1}|T|}$
$\displaystyle\geqslant 25k^{2}\ln d_{k-1}\lvert S\sqcup T\rvert.$

Hence, denoting $c=|S\sqcup T|$,

$\displaystyle\hyperref@@ii[eq:proof-random-lift-first-bound-bad-
event]{\textup{(\ref*{eq:proof-random-lift-first-bound-bad-event})}}\leqslant
2\exp\left(-25ck^{2}\ln d_{k-1}\right)\leqslant d_{k-1}^{-10ck^{2}}.$ (4.3)

We turn to analyze the dependency graph of the “bad” events:444Recall that the
dependency graph of a set of events $\mathfrak{B}$ is a digraph with a vertex
for each event $B\in\mathfrak{B}$ and any event $B$ is mutually independent of
$\mathfrak{B}\setminus\Gamma(B)$. Recall that $\mathfrak{B}$ is the set of all
events $B_{\sigma}^{S,T}$ for $\sigma\in X(k-2)$ and disjoint subsets
$S,T\subseteq X_{\sigma}(0)$. Using the characterization of correlated events
in $\mathfrak{B}$ given in Claim 4.1.1, we get the following bound on the
neighborhood size of the events in the dependency graph:

######  Claim 4.2.1.

Let $B^{S,T}_{\sigma}\in\mathfrak{B}$ and denote $c=|S\sqcup T|$. Then
$B^{S,T}_{\sigma}$ has at most $3k^{2}cd^{c^{\prime}-1}$ neighbors
$B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}$ with $|S^{\prime}\sqcup
T^{\prime}|=c^{\prime}$.

Now, to apply Lovász Local Lemma, one needs to define a function
$\rho:\mathfrak{B}\to[0,1)$ such that

$\operatorname*{\mathbb{P}}\\!\left[B^{S,T}_{\sigma}\right]\leqslant\rho(B^{S,T}_{\sigma})\prod_{B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\sim
B^{x,y}_{\sigma}}\left(1-\rho(B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}})\right).$

Set $\rho(B^{S,T}_{\sigma})=d_{k-1}^{-3ck^{2}}$. Indeed

$\displaystyle\rho(B^{S,T}_{\sigma})\prod_{B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\in\sim
B^{S,T}_{\sigma}}\left(1-\rho(B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}})\right)$
$\displaystyle=d_{k-1}^{-3ck^{2}}\prod_{B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\sim
B^{S,T}_{\sigma}}\left(1-d_{k-1}^{-3|S^{\prime}\cup T^{\prime}|k^{2}}\right)$
$\displaystyle=d_{k-1}^{-3ck^{2}}\prod_{c^{\prime}\in[n]}\left(1-d_{k-1}^{-3c^{\prime}k^{2}}\right)^{2^{c^{\prime}}3ck^{2}d_{k-1}^{c^{\prime}-1}}$
(4.4) $\displaystyle\geqslant
d_{k-1}^{-3ck^{2}}\exp\left(-6ck^{2}\sum_{c^{\prime}\in[n]}2^{c^{\prime}}d_{k-1}^{c^{\prime}-1}d_{k-1}^{-3c^{\prime}k^{2}}\right)$
(4.5) $\displaystyle\geqslant d_{k-1}^{-3ck^{2}}e^{-7ck^{2}}$
$\displaystyle\geqslant
d_{k-1}^{-10ck^{2}}\geqslant\operatorname*{\mathbb{P}}\left[{B_{\sigma}^{S,T}}\right]$
(4.6)

where (4.4) is since for any $U\subseteq X_{\sigma}(0)$ of cardinality
$c^{\prime}$, there are at most $2^{c^{\prime}}$ pairs of disjoint sets
$S^{\prime},T^{\prime}$ with $S^{\prime}\sqcup T^{\prime}=U$, (4.5) is by
$e^{-x}\leqslant 1-\frac{x}{2}$ for any $x\in[0,1.59]$ and (4.6) is by taking
$d_{k-1}\geqslant 3$. Together with (4.3), this concludes the proof. ∎

We are left to prove Claim 4.1.1 and Claim 4.2.1.

###### Proof of Claim 4.1.1.

Recall that

$\displaystyle\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle=\frac{\operatorname{sign}(\hat{\sigma})}{d_{k-1}}\sum_{\tau\in
F(\sigma,S,T)}f(\tau).$ (4.7)

If $B_{\sigma}^{S,T}$ is not mutually independent of $\mathfrak{A}$ then there
exists some $B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\in\mathfrak{A}$ so
that $F(\sigma,S,T)\cap
F(\sigma^{\prime},S^{\prime},T^{\prime})\neq\emptyset$. Hence it is enough to
show that if the two items in Claim 4.1.1 hold, then $F(\sigma,S,T)\cap
F(\sigma^{\prime},S^{\prime},T^{\prime})=\emptyset$ for all
$B^{S^{\prime},T^{\prime}}_{\sigma^{\prime}}\in\mathfrak{A}$.

##### Case $\sigma=\sigma^{\prime}$

Note that $B^{S,T}_{\sigma}$ and $B^{S^{\prime},T^{\prime}}_{\sigma}$ are
events of the same link $X_{\sigma}$. Hence, if $E_{X_{\sigma}}(x,y)\cap
E_{X_{\sigma}}(S^{\prime},T^{\prime})=\emptyset$ then $F(\sigma,S,T)\cap
F(\sigma,S^{\prime},T^{\prime})=\emptyset$.

##### Case $\sigma\neq\sigma^{\prime}$

Clearly, by (4.7), if there is no $k$-face containing both
$\sigma,\sigma^{\prime}$ then $F(\sigma,S,T)\cap
F(\sigma^{\prime},S^{\prime},T^{\prime})=\emptyset$. Otherwise, let
$\tilde{\tau}\in X(k)$ with $\sigma,\sigma^{\prime}\subseteq\tilde{\tau}$ and
note that $f(\tilde{\tau})$ appears in both
$\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\rangle$ and
$\langle\mathbb{1}_{S^{\prime}},A^{f}_{\sigma}\mathbb{1}_{T^{\prime}}\rangle$
(or equivalently $\tilde{\tau}\in F(\sigma,S,T)\cap
F(\sigma^{\prime},S^{\prime},T^{\prime})$), if and only if
$\tilde{\tau}\setminus\sigma\subseteq E_{X_{\sigma}}(S,T)$ and
$\tilde{\tau}\setminus\sigma^{\prime}\subseteq
E_{X_{\sigma^{\prime}}}(S^{\prime},T^{\prime})$. ∎

We now turn to bound the number of events fulfilling each of the cases in
Claim 4.1.1.

###### Proof of Claim 4.2.1.

Fix $S^{\prime},T^{\prime}\subseteq X_{\sigma}^{\prime}(0)$ with
$|S^{\prime}\sqcup T^{\prime}|=c^{\prime}$. Denote the subgraphs of
$X_{\sigma}$ induced by $S,T$ by $G$ and the subgraph induced by
$S^{\prime},T^{\prime}$ on $X_{\sigma^{\prime}}$ by $G^{\prime}$.

We start with bounding the number of neighboring events that consider the same
link as $B^{S,T}_{\sigma}$ does. Since both events are over the same graph, we
are in the same case as in [BL06], and therefore use the same argument: Recall
that we restricted ourselves without loss of generality to connected
subgraphs, and we consider the case that $G$ and $G^{\prime}$ share a common
edge. Hence, one can think of $G^{\prime}$ as a subgraph of $X_{\sigma}$ with
$c^{\prime}$ vertices, with one of its edges in $G$. Therefore, one can bound
the number of such subgraphs by the number of subtrees of $X_{\sigma}$ with
$c^{\prime}$ vertices rooted in $G$. By [Knu68, FM99], the number of such
subtrees is upper bounded by $cd^{c^{\prime}-1}$.

We turn to bound the other case, where $\sigma\neq\sigma^{\prime}$. Fix some
$k$-face given by the second case of Claim 4.1.1 and denote it by
$\tilde{\tau}$. Observe that $\sigma,S,T$ and
$\sigma^{\prime},S^{\prime},T^{\prime}$ are strongly related: there exist
$s,t\in S\sqcup T$ and $s^{\prime},t^{\prime}\in S^{\prime}\sqcup T^{\prime}$
so that
$\tilde{\tau}=\sigma\sqcup\\{s,t\\}=\sigma^{\prime}\sqcup\\{s^{\prime},t^{\prime}\\}$,
and $\\{s,t\\}$, $\\{s^{\prime},t^{\prime}\\}$ are edges in
$E_{X_{\sigma}}(S,T)$, $E_{X_{\sigma}}(S,T)$ respectively. Since
$\sigma\neq\sigma^{\prime}$, one of the following must hold:

  * –

Either there exists $v\in\sigma\cap(S^{\prime}\sqcup T^{\prime})$ so that
$\sigma^{\prime}=(\sigma\setminus\\{v\\})\sqcup\\{s\\}$ and therefore
$\tilde{\tau}\setminus\sigma^{\prime}=\\{v,t\\}$,

  * –

or, both $s^{\prime},t^{\prime}\in\sigma\cap(S^{\prime}\sqcup T^{\prime})$ and
$\sigma^{\prime}=(\sigma\setminus\\{s^{\prime},t^{\prime}\\})\sqcup\\{s,t\\}$,
implying that $\tilde{\tau}\setminus\sigma^{\prime}\subseteq\sigma$.

Hence, we can bound the number of events related to the first case by the
number of subtrees of $X_{\sigma^{\prime}}$ rooted in $\sigma$, that have a
vertex in $S\sqcup T$ and another $c^{\prime}-2$ vertices which is at most
$(k-1)cd^{c^{\prime}-2}$, and the events of the second case by the number of
subtrees having two vertices from $\sigma$ (and rooted in one of them), and
additional $c^{\prime}-2$ vertices which is at most
$(k-1)^{2}d^{c^{\prime}-2}$.

And we get an overall bound of

$\displaystyle
cd^{c^{\prime}-1}+(k-1)cd^{c^{\prime}-2}+(k-1)^{2}d^{c^{\prime}-2}\leqslant
3k^{2}cd^{c^{\prime}-1}.$

∎

###  4.3 Concluding Theorem 4.2

###### Proof of Theorem 4.2.

Let $X$ be a $(d_{0},\ldots,d_{k-1})$-regular, $\lambda(X)$-two sided (resp.
one sided) HDX over $n$ vertices, fix $f$ to be the signing provided by Lemma
4.3, and set $\widehat{X}$ to be the $f$-local lift of $X$.

By Observation 3.2, $\widehat{X}$ is a
$(2d_{0},\ldots,2d_{k-2},d_{k-1})$-regular graph over $2n$ vertices. We need
to prove that for any $\hat{\sigma}\in\widehat{X}$ of dimension $\leqslant
k-2$, the 1-skeleton of $\widehat{X}_{\hat{\sigma}}$ is a
$\max\left\\{\lambda(X),O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)\right\\}$-two
sided (resp. one sided) expander.

By Corollary 3.4, the spectra of all links $\widehat{X}_{\hat{\sigma}}$ with
$\hat{\sigma}$ of dimension $<k-2$ are bounded by $\lambda(X)$. In addition,
by Lemma 4.3, for any $\hat{\sigma}\in\widehat{X}(k-2)$ and any disjoint sets
$S,T\subseteq X_{\sigma}(0)$ for $\sigma=\pi(\hat{\sigma})$, we have that
$|\langle\mathbb{1}_{S},A_{\sigma}^{f}\mathbb{1}_{T}\rangle|\leqslant
O\left(\sqrt{\frac{k^{2}\log d_{k-1}}{d_{k-1}}|S||T|}\right)$ where
$A_{\sigma}^{f}$ is the $f_{\hat{\sigma}}$-signed random walk matrix of
$X_{\sigma}$. Together with Lemma 2.6 this implies

$\displaystyle\lambda(X_{\sigma})=O\left(\sqrt{\frac{k^{2}\log
d_{k-1}}{d_{k-1}}}\left(1+\log\left(\sqrt{\frac{d_{k-1}}{k^{2}\log
d_{k-1}}}\right)\right)\right)$ $\displaystyle\leqslant
O\left(\sqrt{\frac{k^{2}\log d_{k-1}}{d_{k-1}}}\cdot\log\sqrt{d_{k-1}}\right)$
$\displaystyle=O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)$

hence, by Lemma 2.5,
$\lambda(X_{\sigma})=\max\left\\{\lambda(X),O\left(\sqrt{\frac{k^{2}\log^{3}d_{k-1}}{d_{k-1}}}\right)\right\\}$
and by Corollary 3.4, this is also the case for
$\lambda(\widehat{X}_{\hat{\sigma}})$. ∎

##  5 An Algorithmic Version of Theorem 4.1

In this subsection, we prove that there is a randomized algorithm that finds a
family of local lifts as in Theorem 4.1 when $X$ is a high dimensional
expander under mild assumptions on the degree sequence which we encapsulate in
the following definition.

######  Definition 5.1 (Nice complex).

Let $X$ be a $k$-dimensional simplicial complex. We say that $X$ is _nice_ if
$X$ is regular, and

$d_{k-2}^{1-4\log d_{k-1}}<\frac{2}{e(k+1)kd_{k-1}+1}.$ (5.1)

We prove the following.

######  Theorem 5.2.

There exists a randomized algorithm $\mathcal{A}$ that takes as input a
$k$-dimensional complex $X_{0}$ and an integer $i\geqslant 1$, runs in
expected time $\operatorname{poly}((2^{i}|X_{0}(0)|)^{k})$ at most, and
outputs a $k$-dimensional complex $X_{i}$ with $2^{i}|X_{0}(0)|$ vertices. The
algorithm has the following guarantee.

If $X_{0}$ is a nice $(d_{0},\ldots,d_{k-1})$-regular $\lambda$-two sided high
dimensional expander, then $X_{i}$ is a
$(2^{i}d_{0},\dots,2^{i}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two sided
high dimensional expander where

$\lambda^{\prime}=O\left(\max\left\\{\lambda\left(1+\log\frac{1}{\lambda}\right),\sqrt{\frac{\log^{3}d_{k-1}}{d_{k-1}}}\right\\}\right).$

Moreover, one can modify the algorithm so that it outputs a sequence
$X_{1},X_{2},\dots,X_{i}$ of complexes all satisfying the same guarantees
(instead of just the last one), so that for every $j=0,1,\dots,i-1$, $X_{j+1}$
is a local lift of $X_{j}$.

Loosely speaking, in order to prove Theorem 5.2, we need to prove that there
is an algorithm $\mathcal{A}$ that finds a single local lift for $X$ in
polynomial time (just as Theorem 4.1 was proved by the ‘one-step theorem’
Theorem 4.2) with good enough spectral expansion. Then we just iteratively use
$\mathcal{A}$ on its own output, setting $X_{j+1}=\mathcal{A}(X_{j})$, until
reaching $j=i-1$. For this to work, we also need to address the issue that
$\lambda^{\prime}\geqslant\lambda$ so naively the expansion deteriorates as we
reiterate, but this technical discussion is deferred to below.

######  Remark 5.3 (A non-uniform algorithm for any HDX).

Theorem 5.2 requires that $X_{0}$ be a nice complex, i.e. that (5.1) holds.
However, in any family $\left\\{X_{i}\right\\}_{i=0}^{\infty}$ where $X_{i+1}$
is a local lift of $X_{i}$, the degree $d_{k-2}(X_{i})$ tends to infinity with
$i$ while the other side of both inequalities stays fixed. Thus, the
inequalities will eventually hold for any family of consecutive local lifts.
In fact, they should hold for any $i\geqslant C\log(k+d_{k-1}(X_{0}))$ for
some large enough constant $C>0$. Thus we can modify the algorithm to work
even if $X_{0}$ is not nice (albeit with the spectral expansion bound
guaranteed in Theorem 4.1, which is slightly worse than the expansion in
Theorem 5.2). This is done by allowing the algorithm to do a brute-force
search for the first few steps, to produce a nice $X_{i}$, and then continuing
as the original algorithm does. The first few steps will eventually stop
because Theorem 4.1 promises the existence of such an $X_{j}$. This process
takes $\operatorname{poly}(|X_{i}|^{k})+\exp(O(|X_{0}|^{k}))$ time.

Towards the proof of Theorem 5.2, we need the following definition and lemma
from [BL06].

######  Definition 5.4.

A graph $G$ with adjacency operator $A$ is said to be $(\beta,t)$-sparse if
for every $S,T\subseteq V(G)$ such that $|S\cup T|\leqslant t$,

$\left\langle\mathbb{1}_{S},A\mathbb{1}_{T}\right\rangle\leqslant\beta\sqrt{|S||T|}.$

For a $k$-dimensional hyper-regular complex $X$, we say that it is
$(\beta,t)$-sparse if for every $\sigma\in X(k-2)$, the graph $X_{\sigma}$ is
$(\beta,t)$-sparse.

######  Remark 5.5.

While the definition here regards any $S,T$ with $|S\cup T|\leqslant t$, it is
in fact equivalent to regarding only $S,T$ with $|S\cup T|\leqslant t$ _such
that the graph induced on $S\cup T$ is connected_. We also remark that if $X$
is $(\beta,t)$-sparse then it is also $(\beta^{\prime},t)$-sparse for any
$\beta^{\prime}\geqslant\beta$.

The reason we need this definition of sparseness is that in a random local
lift, sparseness does not deteriorate with high probability. More formally,
the following lemma was proven in [BL06].

######  Lemma 5.6 ([BL06, Lemma 3.4]).

Let $G=(V,E)$ be a $d$-regular graph with $n$ vertices that is $(\beta,\log
n)$-sparse for $\beta\geqslant 10\sqrt{\frac{\log d}{d}}$. Then with
probability $\geqslant 1-n^{-4\log d}$ over $f:E\to\left\\{\pm 1\right\\}$:

  * –

For every $S,T\subseteq V$,
$\left\lvert\left\langle\mathbb{1}_{S},A^{f}\mathbb{1}_{T}\right\rangle\right\rvert\leqslant\beta\sqrt{|S||T|}$
and,

  * –

$\widehat{G}^{f}$ is $(\beta,\log{n}+1)$-sparse,

We comment that [BL06, Lemma 3.4] does not explicitly calculate the
probability $1-n^{-4\log d}$; rather, they only say the events happen with
high probability. This is the probability that is implicit in their proof.
They also prove this theorem for $\beta=10\sqrt{\frac{\log d}{d}}$ but the
same proof extends to $\beta\geqslant 10\sqrt{\frac{\log d}{d}}$ with no
additional changes.

This next claim easily follows from the definition of expansion and says that
a spectral expander is sparse.

######  Claim 5.0.1.

Let $G$ be a $d$-regular $\lambda$-two sided spectral expander over $n$
vertices such that $\lambda>\frac{1}{\sqrt{d}}$ and $d\geqslant 3$. Then $G$
is $(2\lambda,\log{n})$-sparse.

###### Proof.

Fix $S,T$ such that with $|S\cup T|\leqslant\log n$. By the
$\lambda$-expansion and the expander mixing lemma (see e.g. [HLW06]),
$\langle\mathbb{1}_{S},A\mathbb{1}_{T}\rangle\leqslant\frac{|S||T|}{n}+\lambda\sqrt{|S||T|}$.
We bound this term by $\left(\lambda+\frac{\log n}{n}\right)\sqrt{|S||T|}$. As
$\frac{\log
n}{n}\leqslant\frac{1}{\sqrt{n}}\leqslant\frac{1}{\sqrt{d}}\leqslant\lambda$
the claim follows. ∎

We are ready to state our one-step theorem.

######  Theorem 5.7.

There exists a randomized algorithm $\mathcal{A}$ with the following
guarantees. Let $X$ be a $k$-dimensional $\bar{d}$-regular $\lambda$-two sided
(resp. one sided) high dimensional expander over $n$ vertices, where
$\bar{d}=(d_{0},\ldots,d_{k-1})$. Let $\beta\geqslant 10\sqrt{\frac{\log
d_{k-1}}{d_{k-1}}}$ and denote by
$\lambda^{\prime}=\max\left\\{\lambda,O(\beta(1+\log\frac{1}{\beta}))\right\\}$.
Assume that $X$ is $(\beta,\log d_{k-2})$-sparse, and suppose that $d_{k-2}$
and $d_{k-1}$ satisfy $d_{k-2}>d_{k-1}^{2}$ and (5.1). Then
$\mathcal{A}(X)=\widehat{X}$ is a local lift of $X$ such that:

  1. 1.

The complex $\widehat{X}$ is a $\lambda^{\prime}$-two sided (resp. one sided)
high dimensional expander.

  2. 2.

The complex $\widehat{X}$ is $(\beta,\log 2d_{k-2})$-sparse.

Upon input $X$ satisfying the above, the algorithm runs in time
$\operatorname{poly}(|X(0)|^{k})$.

Before proving Theorem 5.7, let us quickly prove Theorem 5.2.

###### Proof of Theorem 5.2, assuming Theorem 5.7.

Let $X_{0}$ be as in the assumptions of Theorem 5.2. Let $\mathcal{A}$ be the
randomized algorithm in Theorem 5.7, and let $X_{i+1}=\mathcal{A}(X_{i})$ (or
$X_{i+1}=\bot$ if one of $\mathcal{A}(X_{j})$ fails to terminate for
$j\leqslant i$). It suffices to show the following two statements:

  1. 1.

If $X_{i}\neq\bot$, then $X_{i}$ satisfies:

    1. (a)

$X_{i}$ is a $\lambda^{\prime}$-two sided high dimensional expander.

    2. (b)

$X_{i}$ is $(\beta,\log 2d_{k-2})$-sparse for
$\beta=\max\left\\{2\lambda,10\sqrt{\frac{\log d_{k-1}}{d_{k-1}}}\right\\}$.

    3. (c)

$X_{i}$ is nice, namely (5.1) holds for $X_{i}$.

  2. 2.

For every $i\geqslant 1$, $X_{i}$ is output in expected
$\operatorname{poly}(|X_{i-1}(0)|^{k})$-time. In particular, the probability
that any $\mathcal{A}(X_{i})=\bot$ is $0$.

The first item is proven by induction, where the base case for $X_{0}$ holds
by assumption (the sparseness is also by $\lambda$-two sided spectral
expansion and Lemma 5.6). Assume that $X_{i-1}$ satisfies the three sub-items,
and prove for $X_{i}$. Indeed, $X_{i}=\mathcal{A}(X_{i-1})$ satisfies the
first two sub-items by Theorem 5.7, and satisfies the third item because
$d_{k-2}(X_{i})=2d_{k-2}(X_{i-1})$ and the rest of the parameters remain
fixed. The inequality (5.1) remains true under increasing $d_{k-2}$ so if they
hold true for $X_{i-1}$ they are also true for $X_{i}$.

As for the second item, note that assuming $X_{i-1}$ satisfies the assumptions
Theorem 5.7, the algorithm in Theorem 5.7 runs in expected time
$\operatorname{poly}(|X_{i-1}(0)|^{k})$. ∎

###### Proof of Theorem 5.7.

We intend to use Lemma 2.12. For this, we fix the following ‘bad’ events
$\mathfrak{C}=\left\\{C_{\sigma}\left|\;\vphantom{C_{\sigma}\sigma\in
X(k-2)}\right.\sigma\in X(k-2)\right\\}$ where
$C_{\sigma}\subseteq\left\\{f:X(k)\to\left\\{\pm 1\right\\}\right\\}$ is the
event where :

  1. 1.

Either $\widehat{X_{\sigma}}^{\pm f_{\sigma}}$ is _not_ a
$\lambda^{\prime}$-two sided spectral expander, or

  2. 2.

$\widehat{X_{\sigma}}^{\pm f_{\sigma}}$ is _not_ $(\beta,\log
2d_{k-2})$-sparse.

By Lemma 5.6 (and Lemma 2.6 that relates the first item in Lemma 5.6 to
spectral expansion),
$\operatorname*{\mathbb{P}}_{{f}}\left[C_{\sigma}\right]\leqslant
2d_{k-2}^{-4\log d_{k-1}}$. Moreover, because every link of a
$\hat{\sigma}\in\widehat{X}(k-2)$ is a lift of $X_{\sigma}$ with respect to
$f_{\hat{\sigma}}$, then if none of the events $C_{\sigma}$ occur, then
$\widehat{X}$ satisfies both items in Theorem 5.7. We will use Lemma 2.12 to
find such an assignment.

We now construct a dependency graph for $\mathfrak{C}$. Let $\sigma\in X(k-2)$
and $U\subseteq X(k-2)$. The event $C_{\sigma}$ only depends on $f_{\sigma}$,
so it only depends on $k$-faces $\tau\supseteq\sigma$. Therefore, if
$C_{\sigma}$ and
$\left\\{C_{\sigma^{\prime}}\left|\;\vphantom{C_{\sigma^{\prime}}\sigma^{\prime}\in
U}\right.\sigma^{\prime}\in U\right\\}$ are _not_ mutually independent, then
in particular there is a $k$-face $\tau\in X$ and $\sigma^{\prime}\in U$ such
that $\tau\supseteq\sigma,\sigma^{\prime}$. Hence, in our dependency graph we
connect $C_{\sigma}\sim C_{\sigma^{\prime}}$ if there exists such a $k$-face
containing both $\sigma$ and $\sigma^{\prime}$. Let us upper bound the
neighborhood size of an event $C_{\sigma}$. The number of neighbors that
$C_{\sigma}$ has is upper bounded by the number of $k$-faces containing
$\sigma$ times $\binom{k+1}{k-1}$ (the number of ways to choose
$\sigma^{\prime}\subseteq\tau$). Therefore, the number of neighbors is bounded
by

$D\coloneqq\binom{k+1}{k-1}\cdot\lvert\left\\{\tau\in
X(k)\left|\;\vphantom{\tau\in
X(k)\tau\supseteq\sigma}\right.\tau\supseteq\sigma\right\\}\rvert=\binom{k+1}{k-1}\lvert
X_{\sigma}(1)\rvert=\frac{(k+1)k}{4}d_{k-2}d_{k-1}.$

By setting $\rho:\mathfrak{C}\to[0,1)$ to be the constant function
$\rho(C_{\sigma})=\frac{1}{D+1}$ we have that

$\operatorname*{\mathbb{P}}\left[{C_{\sigma}}\right]\leqslant\rho(C_{\sigma})\prod_{\sigma^{\prime}\sim\sigma}(1-\rho(C_{\sigma})),$

because
$\rho(C_{\sigma})\prod_{\sigma^{\prime}\sim\sigma}(1-\rho(C_{\sigma}))\geqslant\frac{1}{D+1}\left(1-\frac{1}{D+1}\right)^{D}\geqslant\frac{1}{e(D+1)}$
and $\operatorname*{\mathbb{P}}\left[{C_{\sigma}}\right]\leqslant
2d_{k-2}^{-4\log d_{k-1}}\leqslant\frac{1}{e(D+1)}$ by (5.1).

Let us now verify that the algorithm in Lemma 2.12 runs in polynomial time. We
note that there the number of events in $\mathfrak{C}$ is
$\operatorname{poly}(|X(0)|^{k})$, and checking whether $C_{\sigma}$ occurs
could be done in $\operatorname{poly}(|X(0)|)$-time because it amounts to:

  1. 1.

Find the spectrum of a signed adjacency operator of a $d_{k-2}$-sized graph.

  2. 2.

Going over all connected sets $U\subseteq\widehat{X}_{\sigma}^{\pm
f_{\sigma}}$ of size $\leqslant\log 2d_{k-2}$ for every $\sigma\in X(k-2)$,
finding $S,T$ such that $S\cup T=U$, and counting the number of edges between
$S$ and $T$ to check if the pair $S,T$ violates sparseness. There is a
$\operatorname{poly}(|X(0)|)$ such $U,S,T$ at most.

Therefore, the randomized algorithm in Lemma 2.12 will find a signing in
$\operatorname{poly}(|X(0)|^{k})\cdot\sum_{\sigma\in
X(k-2)}\frac{1}{D}=\operatorname{poly}(|X(0)|^{k})$-time. ∎

###  5.1 $1$-Bounded HDX with Arbitrarily Large Constant Vertex Degree

######  Theorem (Restatement of Theorem 1.4).

For every $\lambda>0$ and any sufficiently large $M>0$, there exists an
infinite family of $2$-dimensional $\lambda$-two sided high dimensional
expanders that are
$(d_{0},\exp(\operatorname{poly}(\frac{1}{\lambda})))$-regular, for
$M\leqslant d_{0}\leqslant 2M$.

###### Proof sketch.

Let $\lambda>0$. Let $\tilde{\lambda}$ be such that $\lambda\leqslant
O\left(\tilde{\lambda}(1+\log\frac{1}{\tilde{\lambda}})\right)$ where the
constant in the big $O$ comes from Theorem 5.2. The construction in [FI20]
gives an infinite family of $2$-dimensional $\tilde{\lambda}$-two sided high
dimensional expanders that are $(d_{0},d_{1})$-regular, where
$d_{1}\leqslant\exp(\operatorname{poly}(\frac{1}{\tilde{\lambda}}))$.666See
discussion in [FI20, Section 4.3] on how to do so using $2$-transitive groups.
Denote such a family $\left\\{Y_{\ell}\right\\}_{\ell=0}^{\infty}$. One can
verify that because $d_{0}\geqslant d_{1}+1\geqslant 3$ and $k=2$, these
complexes are indeed nice.

Moreover, let us assume without loss of generality that

$\tilde{\lambda}\left(1+\log\frac{1}{\tilde{\lambda}}\right)\geqslant\frac{\log^{3}d_{1}}{d_{1}},$

since the construction in [FI20] allows to increase the $1$-degree of the
complex by a polynomial in $d_{1}$ while maintaining the
$\tilde{\lambda}$-expansion.

Set $i=\lceil\log(M/d_{0}(Y_{\ell}))\rceil$ (this is a constant since
$d_{0}(Y_{\ell})$ is independent of $\ell$). By applying the algorithm in
Theorem 5.2 with input $(Y_{\ell},i)$, we can obtain a $2$-dimensional
$\lambda$-two sided high dimensional expander $X_{\ell}$ where $d_{1}$ remains
the same but $d_{0}(X_{\ell})=2^{i}d_{0}(Y_{\ell})\in[M,2M]$, thus proving the
theorem. ∎

##  6 Derandomizing the Construction

In this section we provide a deterministic construction of $(k-1)$-bounded
families of high dimensional expanders, as referred to in Theorem 1.3. For the
rest of this section, we denote $\alpha_{k}(d)=10\sqrt{\frac{k^{2}\log d}{d}}$
(when $k$ is clear from context, we will write $\alpha(d)$).

We will prove the following theorem.

######  Theorem 6.1 (Restatement of Theorem 1.3).

There exists a deterministic algorithm $\mathcal{B}$ that takes as input a
$k$-dimensional complex $X_{0}$ and an integer $i\geqslant 1$, runs in time
$\operatorname{poly}((2^{i}|X_{0}(0)|)^{k})$, and outputs a $k$-dimensional
complex $X_{i}$ with $2^{i}|X_{0}(0)|$ vertices. The algorithm has the
following guarantee: If $X_{0}$ is a $(d_{0},\ldots,d_{k-1})$-regular
$\lambda$-two sided high dimensional expander, with
$\lambda>\alpha_{k}(d_{k-1})$, $d_{k-1}>2^{10k}$ and $|X_{0}(k-2)|\leqslant
d_{k-2}^{10k}$, then $X_{i}$ is a
$(2^{i}d_{0},\dots,2^{i}d_{k-2},d_{k-1})$-regular $\lambda^{\prime}$-two sided
high dimensional expander where

$\lambda^{\prime}=O\left(2^{5k}\lambda\left(1+\log\frac{1}{\lambda}\right)\right).$

In particular, for every $n\in\mathbb{N}$, choosing $i=\log n$ yields a
complex with at least $n$-vertices.

This explicit construction generalizes the explicit construction for expanders
given in [BL06], which is based on the conditional probabilities method [AS16,
Chapter 16].

We first observe that under the assumption that the base complex is sparse (as
in Definition 5.4) and that $|X(k-2)|$ is not too large, then a random local
lift of $X$ is also sparse and is a high dimensional expander with high
probability. Then, we explain how we can find such a lift deterministically by
greedily selecting the values $f(\tau)$ one $k$-face at a time.

######  Lemma 6.2.

Let $X$ be a $k$-dimensional, $(d_{0},\ldots,d_{k-1})$-regular and
$(\beta,\log{d_{k-2}})$-sparse simplicial complex so that
$\beta\geqslant\alpha(d_{k-1})$ and $|X(k-2)|\leqslant
d_{k-2}^{\log{d_{k-1}}}$.

Then, for $f:X(k)\to\\{\pm 1\\}$ drawn uniformly at random, with probability
at least $1-d_{k-2}^{-3\log{d_{k-1}}}$:

  1. 1.

For every $\sigma\in X(k-2)$ and every $S,T\subseteq X_{\sigma}(0)$:
$\left\lvert\left\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\right\rangle\right\rvert\leqslant\beta\sqrt{|S||T|}$.

  2. 2.

The local lift $\widehat{X}=\widehat{X}^{f}$ is
$(\beta,\log{d_{k-2}}+1)$-sparse. ∎

We comment that the condition $|X(k-2)|\leqslant d_{k-2}^{\log{d_{k-1}}}$ may
seem odd at first glance. However, similar to Remark 5.3, this is eventually
satisfied by every sequence $\left\\{X_{i}\right\\}_{i=0}^{\infty}$ where
$X_{i+1}$ is a local lift of $X_{i}$. Thus, we do not lose too much generality
by assuming it.

The proof of Lemma 6.2 follows by applying Lemma 5.6 to every link and taking
a union bound over the links. We omit the proof since it is a direct
calculation.

The deterministic construction mentioned at the beginning of this section is
composed of iterative applications of the local lift, where each application
is according to the algorithm described in the following lemma.

######  Lemma 6.3.

Let $X$ be a $k$-dimensional $(d_{0},\ldots,d_{k-1})$-regular
$(\beta,\log{d_{k-2}})$-sparse simplicial complex with $d_{k-1}>2^{10k}$,
$\beta\geqslant\alpha(d_{k-1})$ and such that $|X(k-2)|\leqslant
d_{k-2}^{10k}$.

Then, there is a deterministic $\operatorname{poly}{(|X(0)|^{k})}$ time
algorithm for finding a function $f:X(k)\to\\{\pm 1\\}$ such that:

  1. 1.

For every $\sigma\in X(k-2)$,
$\|A^{f}_{\sigma}\|=O\left(2^{5k}\beta\left(1+\log\frac{1}{\beta}\right)\right)$.

  2. 2.

$\widehat{X}^{f}$ is $(\beta,\log{d_{k-2}}+1)$-sparse.

The proof of Lemma 6.3 uses the method of conditional probabilities. The main
idea is that, given the conditions on the input complex, we can define random
variables denoted $Z^{(\sigma)}$, which serve as “error” indicators, where
these errors occur with very small probability. By defining another set of
random variables $Y^{(\sigma)}$ which correlate with the links’ expansions,
and amplifying the impact of each error, we are able to choose $f(\tau)$
$k$-face by $k$-face, while tracking the expected value of the sum of those
variables efficiently and making sure no error occurs.

We need the following claim, already implicit in [BL06].

######  Claim 6.0.1.

Let $X$ be a hyper-regular $k$-dimensional complex that is $(\beta,t)$-sparse.
Then, for every $f:X(k)\to\\{\pm 1\\}$, $\widehat{X}^{f}$ is
$(\beta,t)$-sparse.

###### Proof of Lemma 6.3.

Denote $m=d_{k-2}$, $d=d_{k-1}$ and
$\beta^{\prime}=\beta\left(1+\log\frac{1}{\beta}\right)$. Our assumption on
$X$ then tells that $|X(k-2)|\leqslant m^{10k}$. Fix $\sigma\in X(k-2)$, and
let $r=2\lceil\log{m}\rceil$.

For using the conditional probabilities method, we define a random variable
$Q=Q(f)$ such that:

  * –

$\operatorname*{\mathbb{E}}[Q(f)]$ can be calculated in
$\operatorname{poly}{(m^{k})}$ time when $f(\tau)$ is fixed on a subset of
$\tau\in X(k)$ and uniformly random on the rest, and

  * –

If $Q(f)\leqslant\operatorname*{\mathbb{E}}[Q(f)]$ then $f$ is _good_ , that
is, it satisfies Item 1 and Item 2 in Lemma 6.3.

Once these conditions are met, we can iteratively assign values to $f$ on the
$k$-faces, calculating the expectation after each assignment such that the
conditional expectation remains smaller than the unconditioned expectation. As
$|X(k)|\leqslant|X(0)|^{k}$, the decision tree for the conditional
probabilities method is of polynomial depth, and we will complete constructing
a good $f$ in polynomial time. Henceforth, the rest of the proof is dedicated
to defining $Q$, such that the above conditions hold. En route to this goal,
we will define two sets of random variables, $Y^{(\sigma)}=Y^{(\sigma)}(f)$
and $Z^{(\sigma)}=Z^{(\sigma)}(f)$, which are intended to define our control
over Item 1 and Item 2, respectively. The variable $Q$ will be the sum over
all $Y^{(\sigma)},Z^{(\sigma)}$.

For any closed walk $p$ of length $r$ in $X_{\sigma}$, we define a random
variable $Y^{(\sigma)}_{p}$ that equals the product of the signs along $p$
according to $f$, divided by $d^{r}$. Note that the expectation of
$Y^{(\sigma)}_{p}$ can be calculated in polynomial time, even when some values
of $f$ have been fixed: if there is at least one unsigned edge with an odd
number of appearances in $p$ then
$\operatorname*{\mathbb{E}}\left[Y^{(\sigma)}_{p}\right]=0$, otherwise as
$\operatorname*{\mathbb{E}}\left[Y^{(\sigma)}_{p}\right]$ is
$\pm\frac{1}{d^{r}}$ according to $f$, even appearances cancel. We also define
$Y^{(\sigma)}=\sum_{p}Y^{(\sigma)}_{p}$, and claim that
$Y^{(\sigma)}=\operatorname{Tr}\left((A^{f}_{\sigma})^{r}\right)$ (where
$\operatorname{Tr}(\cdot)$ is the trace function) since
$\operatorname{Tr}\left((A^{f}_{\sigma})^{r}\right)$ is
$\frac{1}{d^{r}}$-proportional to the sum over walks of length $r$. As $r$ is
even, $\operatorname{Tr}\left((A^{f}_{\sigma})^{r}\right)\geqslant 0$ so
$Y^{(\sigma)}$ is a non-negative random variable. More over, the trace upper
bounds $\lVert A^{f}_{\sigma}\rVert^{r}$ hence upper bounding $Y^{(\sigma)}$
simultaneously for all $\sigma$ will enable us to satisfy Item 1.

By the first item in Lemma 6.2 combined with Lemma 2.6, with probability at
least $1-m^{-3\log{d}}$ the lift is a $\left(C_{0}\beta^{\prime}\right)$-two
sided high dimensional expander for some constant $C_{0}$. Since the trace of
a matrix equals the sum of its eigenvalues, we get, in this case, that

$Y^{(\sigma)}=\operatorname{Tr}((A^{f}_{\sigma})^{r})\leqslant
m\left(C_{0}\beta^{\prime}\right)^{r}\leqslant\left(C_{1}\beta^{\prime}\right)^{r},$

where $C_{1}$ is some constant.

As for any $f$ it holds that $\|A^{f}_{\sigma}\|\leqslant 1$, we get that
$Y^{(\sigma)}(f)\leqslant m$, and overall

$\operatorname*{\mathbb{E}}\left[Y^{(\sigma)}\right]\leqslant\left(C_{1}\beta^{\prime}\right)^{r}+m^{-3\log{d}}\cdot
m\leqslant\left(C_{2}\beta^{\prime}\right)^{r}$

for some constant $C_{2}$.

We turn towards defining our second random variable $Z^{(\sigma)}$. Let
$\gamma$ be a constant defined later in the proof. For every $S,T\subseteq
X_{\sigma}(0)$ with $|S\cup T|=\log{m}+1$ and the graph induced by $S$ and $T$
on in $X_{\sigma}$ is connected, we define

$Z^{(\sigma)}_{S,T}=\begin{cases}\gamma,&\text{if
}\left\lvert\left\langle\mathbb{1}_{S},A^{f}_{\sigma}\mathbb{1}_{T}\right\rangle\right\rvert>\beta\sqrt{|S||T|},\\\
0,&\text{otherwise}.\end{cases}$

As in the proof of Lemma 4.3 (see (4.3)), the probability
$\operatorname*{\mathbb{P}}[Z^{(\sigma)}_{S,T}>0]<d^{-10k^{2}\log{m}}$ and
therefore

$\operatorname*{\mathbb{E}}\left[Z^{(\sigma)}_{S,T}\right]\leqslant
d^{-10k^{2}\log{m}}\cdot\gamma.$

We also define $Z^{(\sigma)}=\sum_{S,T}Z^{(\sigma)}_{S,T}$. As in the proof of
4.2.1, there are at most $m(3d)^{\log{m}+1}<d^{3\log m}$ pairs $S,T$ with
$|S\cup T|=\log{m}+1$ that induce a connected subgraph, since we can bound the
number of such pairs using the number of subtrees of $X_{\sigma}$ with
$\log{m}+1$ vertices rooted in $X_{\sigma}$ (times the number of ways to
choose sets $S,T$ that span the tree). Overall, we get that

$\operatorname*{\mathbb{E}}\left[Z^{(\sigma)}\right]\leqslant d^{3\log
m}\cdot\operatorname*{\mathbb{E}}\left[Z^{(\sigma)}_{S,T}\right]\leqslant
d^{-3k^{2}r}\cdot\gamma.$

Note that like the variables $Y_{p}$, the expectation of $Z^{(\sigma)}_{S,T}$
can be calculated in polynomial time even for partial assignments for the
values of $f$, as the number of $S,T$ involved in the summation is bounded by
a polynomial in $m^{k}$. Notice also that when $Z^{(\sigma)}(f)=0$, Item 2 in
Lemma 6.3 holds true: $Z^{(\sigma)}_{S,T}$ implies that the sparsity
inequality holds for all pairs $S,T$ of size $\log{m}+1$ that induce a
connected subgraph. For sets with support less or equal to $\log m$, sparsity
holds by 6.0.1. Thus by Remark 5.5 the lift is $(\beta,1+\log m)$-sparse.

We next define $Q^{(\sigma)}=Y^{(\sigma)}+Z^{(\sigma)}$, and set
$\gamma=\left(C_{2}\beta^{\prime}d^{3k^{2}}\right)^{r}$. Notice that

$\operatorname*{\mathbb{E}}[Q^{(\sigma)}]=\operatorname*{\mathbb{E}}[Y^{(\sigma)}]+\operatorname*{\mathbb{E}}[Z^{(\sigma)}]\leqslant
2\left(C_{2}\beta^{\prime}\right)^{r}.$

We can now define $Q=\sum_{\sigma\in X(k-2)}Q^{(\sigma)}$ and get

$\operatorname*{\mathbb{E}}[Q]\leqslant|X(k-2)|\cdot
2\left(C_{2}\beta^{\prime}\right)^{r}\leqslant
2m^{10k}\left(C_{2}\beta^{\prime}\right)^{r}\leqslant 2\cdot
2^{5kr}\left(C_{2}\beta^{\prime}\right)^{r}<\gamma.$ (6.1)

We claim that if $Q$ is less or equal to its expectation, both Item 1 and Item
2 hold. Indeed, $Z^{(\sigma)}=0$ for every $\sigma\in X(k-2)$, as the minimal
non-zero value of $Z^{(\sigma)}$ is $\gamma$. We further note that in this
case, taking into account the non-negativity of the $Y^{(\sigma)}$-s,

$Y^{(\sigma)}\leqslant Q\leqslant\operatorname*{\mathbb{E}}[Q]\leqslant 2\cdot
2^{5kr}\left(C_{2}\beta^{\prime}\right)^{r}$

for every $\sigma\in X(k-2)$, and hence

$\lVert
A^{f}_{\sigma}\rVert\leqslant\left(Y^{(\sigma)}\right)^{\frac{1}{r}}\leqslant
2\cdot 2^{5k}\left(C_{2}\beta^{\prime}\right),$

therefore Item 1 is satisfied as well. ∎

We are now ready to prove our main result in this section.

###### Proof of Theorem 6.1.

Let $\bar{d}=(d_{0},d_{1},\dots,d_{k-1}=d)$ and let $X_{0}$ be a
$\bar{d}$-regular $\lambda$-two sided high dimensional expander for
$\lambda>\alpha_{k}(d)$, such that $|X_{0}(k-2)|\leqslant d_{k-2}^{10k}$. By
Claim 5.0.1, it is also $(2\lambda,\log{d_{k-2}})$-sparse.

Denote by $\mathcal{B^{\prime}}$ the algorithm suggested by Lemma 6.3, and let
$X_{1},X_{2},\dots,X_{i}$ be such that $X_{j}=\mathcal{B^{\prime}}(X_{j-1})$
for $j\in[i]$. We set $X_{i}$ to be $\mathcal{B}$’s output.

Let us show that, $X_{i}$ meets the guarantees of Theorem 6.1. By 3.2, for
every $j\in[i]$, $X_{j}$ is
$(2^{j}d_{0},2^{j}d_{1},\dots,2^{j}d_{k-2},d)$-regular and
$|X_{j}(0)|=2^{j}|X_{0}(0)|$.

In addition, one can verify by a direct calculation that, for any $j\in[i]$,
$|X_{j}(k-2)|=2^{k-1}|X_{j-1}(k-2)|$, so if $|X_{j-1}(k-2)|\leqslant
d_{k-2}(X_{j-1})^{10k}$ then

$|X_{j}(k-2)|=2^{k-1}|X_{j-1}(k-2)|\leqslant d_{k-2}(X_{j-1})^{10k}\cdot
2^{k-1}\leqslant d_{k-2}(X_{j})^{10k}.$

Thus, by induction and the fact that this inequality holds for $X_{0}$, this
holds for every $j$.

Finally, by Lemma 6.3 one inductively obtains that for any $j$:

  1. 1.

$X_{j}$ is an
$O\left(2^{5k}\lambda\left(1+\log\frac{1}{\lambda}\right)\right)$-high
dimensional expander.

  2. 2.

$X_{j}$ is $\left(2\lambda,\log{d_{k-2}(X_{i})}\right)$-sparse.

  3. 3.

$X_{j}$ computed in time
$\operatorname{poly}(|X_{j-1}(0)|^{k})=\operatorname{poly}(2^{j-1}|X_{0}(0)|^{k})$.

as required. ∎

## References

  * [ABN23] Anurag Anshu, Nikolas P Breuckmann and Chinmay Nirkhe  “NLTS Hamiltonians from good quantum codes”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , 2023, pp. 1090–1096
  * [AG10] Louigi Addario-Berry and Simon Griffiths  “The spectrum of random lifts”  In _arXiv preprint arXiv:1012.4097_ , 2010
  * [AKM13] Naman Agarwal, Alexandra Kolla and Vivek Madan  “Small Lifts of Expander Graphs are Expanding”  In _CoRR_ abs/1311.3268, 2013  arXiv: http://arxiv.org/abs/1311.3268
  * [AL02] Alon Amit and Nathan Linial  “Random graph coverings I: General theory and graph connectivity”  In _Combinatorica_ 22.1 Springer, 2002, pp. 1–18
  * [Ami+01] Alon Amit, Nathan Linial, Jirí Matousek and Eyal Rozenman  “Random lifts of graphs”  In _Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2001, pp. 883–894  DOI: 10.1145/365411.365801
  * [Ana+19] Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant  “Log-concave polynomials II: high-dimensional walks and an FPRAS for counting bases of a matroid”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019, pp. 1–12
  * [AS16] Noga Alon and Joel H Spencer  “The probabilistic method”  John Wiley & Sons, 2016
  * [Bal00] Cristina M Ballantine  “Ramanujan type buildings”  In _Canadian Journal of Mathematics_ 52.6 Cambridge University Press, 2000, pp. 1121–1148
  * [BB89] Aart Blokhuis and Andries E Brouwer  “Locally 4-by-4 grid graphs”  In _Journal of graph theory_ 13.2 Wiley Online Library, 1989, pp. 229–244
  * [BC75] Morton Brown and Robert Connelly  “On graphs with a constant link, II”  In _Discrete Mathematics_ 11.3 Elsevier, 1975, pp. 199–232
  * [BL06] Yehonatan Bilu and Nathan Linial  “Lifts, Discrepancy and Nearly Optimal Spectral Gap”  In _Combinatorica_ 26.1439-6912, 2006, pp. 495–519  DOI: https://doi.org/10.1007/s00493-006-0029-7
  * [BLM24] Mitali Bafna, Noam Lifshitz and Dor Minzer  “Constant Degree Direct Product Testers with Small Soundness”, 2024  eprint: arXiv:2402.00850
  * [BM23] Mitali Bafna and Dor Minzer  “Characterizing Direct Product Testing via Coboundary Expansion”, 2023
  * [Bor20] Charles Bordenave  “A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts”  In _Ann. Sci. Éc. Norm. Supér. (4)_ 53.6, 2020, pp. 1393–1439  DOI: 10.24033/asens.2450
  * [CL23] Michael Chapman and Alexander Lubotzky  “Stability of Homomorphisms, Coverings and Cocycles II: Examples, Applications and Open problems”  In _arXiv preprint arXiv:2311.06706_ , 2023
  * [CLY20] Michael Chapman, Nathan Linial and Peled Yuval  “Expander Graphs — Both Local and Global”  In _Combinatorica_ 40, 2020, pp. 473–509  DOI: 10.1007/s00493-019-4127-8
  * [Con19] David Conlon  “Hypergraph expanders from Cayley graphs”  In _Israel Journal of Mathematics_ 233.1 Springer, 2019, pp. 49–65
  * [CSŻ03] Donald I Cartwright, Patrick Solé and Andrzej Żuk  “Ramanujan geometries of type An”  In _Discrete mathematics_ 269.1-3 Elsevier, 2003, pp. 35–43
  * [CTZ20] David Conlon, Jonathan Tidor and Yufei Zhao  “Hypergraph expanders of all uniformities from Cayley graphs”  In _Proceedings of the London Mathematical Society_ 121.5 Wiley Online Library, 2020, pp. 1311–1336
  * [DD23] Yotam Dikstein and Irit Dinur  “Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers”, 2023  eprint: arXiv:2308.09582
  * [DDL24] Yotam Dikstein, Irit Dinur and Alexander Lubotzky  “Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs”, 2024  URL: https://eccc.weizmann.ac.il/report/2024/019/
  * [Dik22] Yotam Dikstein  “New High Dimensional Expanders from Covers”, 2022
  * [Din+22] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky and Shahar Mozes  “Locally testable codes with constant rate, distance, and locality”  In _Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing_ , 2022, pp. 357–374
  * [Din07] Irit Dinur  “The PCP theorem by gap amplification”  In _J. ACM_ 54.3, 2007, pp. 12  DOI: 10.1145/1236457.1236459
  * [DK17] Irit Dinur and Tali Kaufman  “High dimensional expanders imply agreement expanders”  In _Proc. $58$th IEEE Symp. on Foundations of Comp. Science (FOCS)_, 2017, pp. 974–985  DOI: 10.1109/FOCS.2017.94
  * [DLZ23] Irit Dinur, Siqi Liu and Rachel Yun Zhang  “New Codes on High Dimensional Expanders”, 2023  eprint: arXiv:2308.15563
  * [EL75] Paul Erdős and László Lovász  “Problems and results on 3-chromatic hypergraphs and some related questions, in “Infinite and Finite Sets”(A. Hajnal et al., Eds.)”  In _Colloq. Math. Soc. J. Bolyai_ 11, 1975, pp. 609
  * [FI20] Ehud Friedgut and Yonatan Iluz  “Hyper-regular graphs and high dimensional expanders”, 2020  eprint: arXiv:2010.03829
  * [FM99] Alan M Frieze and Michael Molloy  “Splitting an expander graph”  In _Journal of Algorithms_ 33.1 Elsevier, 1999, pp. 166–172
  * [Fox+12] Jacob Fox, Mikhail Gromov, Vincent Lafforgue, Assaf Naor and János Pach  “Overlap properties of geometric expanders”  In _Journal für die reine und angewandte Mathematik (Crelles Journal)_ 2012.671 De Gruyter, 2012, pp. 49–83
  * [Fri08] Joel Friedman  “A proof of Alon’s second eigenvalue conjecture and related problems”  American Mathematical Soc., 2008
  * [GK22] Roy Gotlib and Tali Kaufman  “List Agreement Expansion from Coboundary Expansion”, 2022  eprint: arXiv:2210.15714
  * [GK23] Roy Gotlib and Tali Kaufman  “No Where to Go But High: A Perspective on High Dimensional Expanders”  In _arXiv e-prints_ , 2023, pp. arXiv–2304
  * [Gol11] Oded Goldreich  “A sample of samplers: A computational perspective on sampling”  In _Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman_ Springer, 2011, pp. 302–332
  * [Gol21] Louis Golowich  “Improved Product-Based High-Dimensional Expanders”  In _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)_ 207, 2021  DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.38
  * [Gol23] Louis Golowich  “From Grassmannian to Simplicial High-Dimensional Expanders”  In _arXiv preprint arXiv:2305.02512_ , 2023
  * [Gro10] M. Gromov  “Singularities, Expanders and Topology of Maps. Part 2: from Combinatorics to Topology Via Algebraic Isoperimetry”  In _Geom. Funct. Anal._ 20, 2010, pp. 416–526  DOI: 10.1007/s00039-010-0073-8
  * [HLW06] Shlomo Hoory, Nathan Linial and Avi Wigderson  “Expander graphs and their applications”  In _Bulletin of the American Mathematical Society_ 43.4, 2006, pp. 439–561
  * [Kee14] Peter Keevash  “The existence of designs”  In _arXiv preprint arXiv:1401.3665_ , 2014
  * [KL14] Tali Kaufman and Alexander Lubotzky  “High dimensional expanders and property testing”  In _Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014_ , 2014, pp. 501–506
  * [Knu68] Donald E. Knuth  “The art of computer programming. Vol. 1: Fundamental algorithms.”  Addison-Wesley Publishing Company Inc, 1968
  * [KO18] Tali Kaufman and Izhar Oppenheim  “Construction of new local spectral high dimensional expanders”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018_ , 2018, pp. 773–786
  * [Li04] Wen-Ching Winnie Li  “Ramanujan hypergraphs”  In _Geometric & Functional Analysis GAFA_ 14 Springer, 2004, pp. 380–399
  * [Liu+23] Siqi Liu, Sidhanth Mohanty, Tselil Schramm and Elizabeth Yang  “Local and Global Expansion in Random Geometric Graphs”  In _Proceedings of the 55th Annual ACM Symposium on Theory of Computing_ , STOC 2023  Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 817–825  DOI: 10.1145/3564246.3585106
  * [LLR19] Alexander Lubotzky, Zur Luria and Ron Rosenthal  “Random Steiner systems and bounded degree coboundary expanders of every dimension”  In _Discrete & Computational Geometry_ 62 Springer, 2019, pp. 813–831
  * [LM06] Nathan Linial and Roy Meshulam  “Homological Connectivity Of Random 2-Complexes”  In _Combinatorica_ 26, 2006, pp. 475–487  DOI: 10.1007/s00493-006-0027-9
  * [LMY20] Siqi Liu, Sidhanth Mohanty and Elizabeth Yang  “High-Dimensional Expanders from Expanders”  In _11th Innovations in Theoretical Computer Science Conference (ITCS 2020)_ , 2020
  * [LPS88] Alexander Lubotzky, Ralph Phillips and Peter Sarnak  “Ramanujan graphs”  In _Combinatorica_ 8.3, 1988, pp. 261–277
  * [LSV05] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Explicit constructions of Ramanujan complexes of type $\tilde{A_{d}}$”  In _European J. Combin._ 26.6, 2005, pp. 965–993  DOI: 10.1016/j.ejc.2004.06.007
  * [LSV05a] Alexander Lubotzky, Beth Samuels and Uzi Vishne  “Ramanujan complexes of type $\tilde{A_{d}}$”  In _Israel J. Math._ 149.1, 2005, pp. 267–299  DOI: 10.1007/BF02772543
  * [Lub18] Alexander Lubotzky  “High dimensional expanders”  In _Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018_ , 2018, pp. 705–730  World Scientific
  * [Már+03] A. Márquez, A. de Mier, M. Noy and M.P. Revuelta  “Locally grid graphs: classification and Tutte uniqueness” The 18th British Combinatorial Conference  In _Discrete Mathematics_ 266.1, 2003, pp. 327–352  DOI: https://doi.org/10.1016/S0012-365X(02)00818-X
  * [MAR73] GREGORY MARGULIS  “Explicit constructions of expanders”  In _Problemy Peredaci Informacii_ 9.4, 1973, pp. 71–80
  * [MSS15] Adam W. Marcus, Daniel A. Spielman and Nikhil Srivastava  “Interlacing families I: Bipartite Ramanujan graphs of all degrees”  In _Annals of Mathematics_ 182, 2015, pp. 307–325  DOI: 10.4007/annals.2015.182.1.7
  * [MT10] Robin A Moser and Gábor Tardos  “A constructive proof of the general Lovász local lemma”  In _Journal of the ACM (JACM)_ 57.2 ACM New York, NY, USA, 2010, pp. 1–15
  * [MW09] Roy Meshulam and N. Wallach  “Homological connectivity of random _k_ -dimensional complexes”  In _Random Struct. Algorithms_ 34.3, 2009, pp. 408–417  DOI: 10.1002/rsa.20238
  * [Oli09] Roberto Imbuzeiro Oliveira  “The spectrum of random k-lifts of large graphs (with possibly large k)”  In _arXiv preprint arXiv:0911.4741_ , 2009
  * [OP22] Ryan O’Donnell and Kevin Pratt  “High-Dimensional Expanders from Chevalley Groups”  In _37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA_ 234, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, pp. 18:1–18:26  DOI: 10.4230/LIPIcs.CCC.2022.18
  * [PK22] Pavel Panteleev and Gleb Kalachev  “Asymptotically good Quantum and locally testable classical LDPC codes”  In _STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022_ ACM, 2022, pp. 375–388  DOI: 10.1145/3519935.3520017
  * [Rei08] Omer Reingold  “Undirected connectivity in log-space”  In _Journal of the ACM (JACM)_ 55.4 ACM New York, NY, USA, 2008, pp. 1–24
  * [RVW02] Omer Reingold, Salil Vadhan and Avi Wigderson  “Entropy waves, the zig-zag graph product, and new constant-degree expanders”  In _Annals of mathematics_ 155.1, 2002, pp. 157–187
  * [SS96] Michael Sipser and Daniel A Spielman  “Expander codes”  In _IEEE transactions on Information Theory_ 42.6 IEEE, 1996, pp. 1710–1722
  * [Sur84] David Surowski  “Covers of simplicial complexes and applications to geometry”  In _Geometriae Dedicata_ 16, 1984, pp. 35–62  DOI: 10.1007/BF00147420
  * [Ta-17] Amnon Ta-Shma  “Explicit, almost optimal, epsilon-balanced codes”  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , 2017, pp. 238–251