# Simple Constructions of Unique Neighbor Expanders
from Error-correcting Codes

Swastik Kopparty Department of Mathematics and Department of Computer Science,
University of Toronto<EMAIL_ADDRESS>Supported by an
NSERC discovery grant. Noga Ron-Zewi Department of Computer Science,
University of Haifa. Email<EMAIL_ADDRESS>Supported in part by ISF
grant 735/20 and by the European Union (ERC, ECCC, 101076663). Views and
opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research
Council. Neither the European Union nor the granting authority can be held
responsible for them. Shubhangi Saraf Department of Mathematics and Department
of Computer Science, University of Toronto<EMAIL_ADDRESS>Supported by an NSERC discovery grant.

###### Abstract

In this note, we give very simple constructions of unique neighbor expander
graphs starting from spectral or combinatorial expander graphs of mild
expansion. These constructions and their analysis are simple variants of the
constructions of LDPC error-correcting codes from expanders, given by Sipser-
Spielman [SS96] (and Tanner [Tan81]), and their analysis. We also show how to
obtain expanders with many unique neighbors using similar ideas.

There were many exciting results on this topic recently, starting with
Asherov-Dinur [AD23] and Hsieh-McKenzie-Mohanty-Paredes [HMMP23], who gave a
similar construction of unique neighbor expander graphs, but using more
sophisticated ingredients (such as almost-Ramanujan graphs) and a more
involved analysis. Subsequent beautiful works of Cohen-Roth-TaShma [CRT23] and
Golowich [Gol23] gave even stronger objects (lossless expanders), but also
using sophisticated ingredients.

The main contribution of this work is that we get much more elementary
constructions of unique neighbor expanders and with a simpler analysis.

##  1 Introduction

This paper is about bipartite expander graphs, and we begin by introducing
some relevant notions of expansions.

Let $G$ be a bipartite graph with left set $L$, right set $R$, and where all
vertices in $L$ have degree $d$. $G$ is called a
$(\delta,\alpha)$-(combinatorial) expander for $\delta,\alpha>0$ if for any
subset $S\subseteq L$ of size at most $\delta|L|$, the set $\Gamma(S)$ of
neighbors of $S$ has size at least $\alpha d|S|$ (this is a constant fraction
of the maximum possible: $d|S|$). $G$ is called a lossless expander if
$\alpha=1-\varepsilon$ for a small $\varepsilon>0$. Since for a small
$\varepsilon>0$, $\Gamma(S)$ is almost as big as $d|S|$ (which is the number
of edges incident on $S$), almost every vertex in $\Gamma(S)$ has a unique
neighbor in $S$. This brings us to the definition of unique neighbor
expanders.

A bipartite graph $G$ as above is called a $\delta$-_unique neighbor expander_
if for any subset $S\subseteq L$ of size at most $\delta|L|$, there is some
vertex in $R$ which is adjacent to exactly one element of $S$. A stronger
variant of this definition is a $(\delta,\alpha)$-_unique neighbor expander_ ,
which asks for the existence of $\alpha d|S|$ vertices in $R$ that are each
adjacent to exactly one element of $|S|$. As mentioned above, lossless
expanders are (strong) unique neighbor expanders. In particular, the following
fact is well-known.

######  Fact 1.1.

Suppose that $G$ is a $(\delta,1-\varepsilon)$-combinatorial expander. Then
$G$ is also a $(\delta,1-2\varepsilon)$-unique neighbor expander.

Note that the above fact is only meaningful when $\varepsilon<\frac{1}{2}$.

###  1.1 History: Unique Neighbor Expanders and Codes

Unique neighbor expanders are of significant interest in coding theory because
they immediately lead to nice error-correcting codes [SS96] (we will shortly
elaborate on this connection). They also have applications in the construction
of locally testable codes [DSW06, BV09]. In addition to coding theory, unique
neighbor expanders have found applications for routing problems in online
settings and for load balancing problems [PU89, ALM96, Pip96, AC02]. See
[AD23] for a discussion of several nice applications of unique neighbor
expanders. For now we will focus on the application of unique neighbor
expanders to codes, since it is precisely the connection to the construction
of codes using expanders that inspired our construction of unique neighbor
expanders.

In their fundamental paper [SS96], Sipser and Spielman proposed several
constructions of Low Density Parity Check (LDPC) codes based on sufficiently
good expanders. We start by describing the simplest such construction from
that paper, which we call SS1.

#### SS1:

Take an _unbalanced_ bipartite graph $G$ with $n$ vertices on the left and
$\beta n$ vertices on the right for some $\beta\in(0,1)$. The left vertices
$u$ will index codeword coordinates; we will write bits $x_{u}$ on these
vertices. The right vertices $v$ will represent constraints on these
coordinates; each right vertex $v$ will ask that the parity of all the bits
$x_{u}$ written on the neighbors $u$ of $v$ should equal $0$. The resulting
codewords $x\in\\{0,1\\}^{n}$ form a linear code $C[G]$, and we call $G$ the
_parity-check graph_ of the resulting code $C[G]$.

Now if $G$ is a _unique neighbor expander_ , then we get that for any $x$ of
low weight, there is some right vertex $v$ that is adjacent to exactly one
nonzero coordinate of $x$, and thus the constraint of $v$ is violated. This
implies that low weight strings $x$ cannot be codewords, and thus the code has
good distance. Since $\beta<1$, the code also has $\Omega(n)$ dimension, and
thus also has good rate. Furthermore, if $G$ has bounded right degree, then
the obtained codes are Low Density Parity Check (LDPC) codes, since they are
defined by parity constraints involving few variables.

At that time, there were no explicit constructions of unique neighbor
expanders, and thus the SS1 expander-to-code transformation of Sipser and
Spielman did not lead to explicit error-correcting codes. The construction of
explicit unique neighbor expanders was an important open question left by
their work. Nevertheless, Sipser and Spielman gave a different construction
(related to a construction of Tanner [Tan81]) of codes from expander graphs,
and it turned out that this construction required just moderate expansion, and
could thus be made explicit from what was known then. We describe this
construction, which we will call SS2, below.

#### SS2:

For this construction, we start with a bipartite graph $G$ with $n$ vertices
on the left and $\beta n$ vertices on the right (for some $\beta\in(0,1)$),
with left and right degrees $d$ and $d/\beta$, respectively, as well as a
constant size linear code $C_{0}\subseteq\\{0,1\\}^{d/\beta}$. The codewords
of the new code $C[G,C_{0}]$ are again formed out of bits $x_{u}$ written on
the left vertices, but this time they have to obey the constraint that for
every right vertex $v$, the string $(x_{u})_{u\in\Gamma(v)}$ should be a
codeword of $C_{0}$. Note that the SS1 construction is just the special case
where $C_{0}$ is the parity code (i.e., the codewords are all strings of even
parity).

It was shown by Sipser and Spielman that if $G$ is a _combinatorial expander_
with only a moderate (non-lossless) expansion, and $C_{0}$ has sufficient
distance in terms of this expansion, then the code $C[G,C_{0}]$ has a good
distance. The analysis is a generalization of the simple argument given above
for the special case where $C_{0}$ is the parity code. Specifically, it can be
shown that if $G$ is a combinatorial expander with moderate expansion, then
for any $x$ of low weight, there is some right vertex $v$ that is adjacent to
a _small number_ of nonzero coordinates of $x$, and thus the constraint of $v$
is violated, assuming that $C_{0}$ has a sufficiently large distance.

In their paper, Sipser and Spielman also gave an alternate construction, in
which $G$ is the edge-vertex incidence graph111The _edge-vertex incidence
graph_ of a graph $G=(V,E)$ is the bipartite graph $G^{\prime}=(L\cup
R,E^{\prime})$, where $L=E$, $R=V$, and $(e,v)\in E^{\prime}$ if $v$ is one of
the endpoints of $e$ in $G$. of a _spectral expander_ of mild expansion (i.e.,
a (non-bipartite) regular graph of bounded second normalized eigenvalue). In
this case, the above analysis follows using the expander mixing lemma.

Several years later, the first explicit unique neighbor expanders that allowed
an instantiation of the SS1 construction were discovered. This was first done
by Capalbo, Reingold, Vadhan and Wigderson [CRVW02], who constructed lossless
expanders (which are also unique neighbor expanders by Fact 1.1), with any
constant imbalance $\beta=|R|/|L|>0$, via a variant of the zig-zag product of
[RVW00]. At around the same time, Alon and Capalbo [AC02] gave a much cleaner
construction of unique neighbor expanders222They also gave explicit
constructions of the more difficult non-bipartite unique neighbor expanders.,
by composing a 44-regular Ramanujan graph333Ramanujan graphs are extremal
graphs with the best possible spectral expansion. with a certain special (43,
21)-vertex bipartite graph. Because of the specialized nature of this
construction, it could only give unique neighbor expanders with imbalance
$\beta=21/22$.

Recently, interest in this topic was revived in a beautiful work of Asherov
and Dinur [AD23], who abstracted out the essential features of the Alon-
Capalbo construction. Specifically, they showed how to compose an "outer"
large bipartite Ramanujan graph $G_{\mathrm{out}}$, together with an "inner"
constant sized unique neighbor expander $G_{\mathrm{in}}$ (which can be found
via brute force search), to get a large unique neighbor expander
$G_{\mathrm{out}}\circ G_{\mathrm{in}}$, with any constant imbalance
$\beta>0$. The composition was made via the _routed product_ , that was
already implicit in [AC02], and formally defined in [AD23]. As pointed out in
[AD23], the routed product $G_{\mathrm{out}}\circ G_{\mathrm{in}}$ is simply
the parity-check graph of the SS2 construction $C[G,C_{0}]$, where
$G=G_{\mathrm{out}}$ and $C_{0}=C[G_{\mathrm{in}}]$. However, as opposed to
SS2, the analysis of [AD23] was surprisingly subtle, and required the full
Ramanujan property (i.e, the smallest possible second normalized eigenvalue)
of the outer graph.

An independent beautiful work of Hsieh-McKenzie-Mohanty-Paredes [HMMP23] gave
strong unique neighbor expanders (where small sets have many unique
neighbors), with expansion from both the left and the right. Further, their
construction just used nearly Ramanjuan graphs (which are also Cayley graphs)
as an ingredient, and did not need the full Ramanujan property. Subsequent
work of Cohen-Roth-TaShma [CRT23] and Golowich [Gol23] gave much stronger
objects (lossless expanders), with a very elegant construction and analysis,
while also using significantly more powerful pseudorandom objects as
ingredients such as high-dimensional expanders.

###  1.2 Our result: Unique Neighbor Expanders from Codes

The main focus of this paper is to give simple and elementary constructions of
unique neighbor expanders.

The very high level inspiration for our construction comes from considering
how we can construct an LDPC code with good distance. One approach is to use
the SS1 construction $C[G]$ with a unique neighbor expander $G$ – but these
are hard to construct. Another approach is to take the SS2 code construction
$C[G,C_{0}]$ with an easier to construct expander $G$ and some constant size
code $C_{0}$. We show that this second approach can help us instantiate the
first approach.

In the SS2 construction, let us choose the constant sized inner code $C_{0}$
to be the SS1 construction code $C[G_{0}]$ coming from a constant sized unique
neighbor expander $G_{0}$. The resulting SS2 code $C^{*}=C[G,C_{0}]$ is an
LDPC code with good distance. As mentioned above, $C^{*}$ can also be obtained
from the SS1 construction directly; namely by applying the SS1 construction to
the routed product graph $G\circ G_{0}$. If for some reason $G\circ G_{0}$
happened to be a unique neighbor expander, this would give another explanation
why $C^{*}$ is an LDPC code with good distance. Following this trail of clues,
we show that indeed, $G\circ G_{0}$ is a unique neighbor expander. The
analysis is very similar to that of SS2, showing that $C^{*}=C[G,C_{0}]$ is an
LDPC code with good distance.

Opening this up (and staying away from too much coding jargon), it amounts to
the following. As in [AD23], we use the routed product, with the inner graph
being a constant sized unique neighbor expander (which can be found via brute-
force search). However, following the SS2 construction, we choose the outer
graph to be either the edge-vertex incidence graph of a spectral expander with
mild expansion, or a combinatorial expander with moderate expansion.

In more detail, in our first construction, given in Section 3, we use as an
outer graph the edge-vertex incidence graph of a spectral expander with a
sufficiently small constant second normalized eigenvalue. Such graphs can be
explicitly constructed for example by taking graph powers of an infinite
family of regular spectral expanders of some constant second normalized
eigenvalue (for example those of Gabber and Galil [GG81]), or, alternatively,
using (a simple version of) the zig-zag product [RVW00] (see also the survey
[Vad12], Section 4.3). We show that this choice of an outer graph gives the
following explicit construction of arbitrarily unbalanced strong unique
neighbor expanders.

######  Theorem 1.2.

For any constant $\beta\in(0,1]$, there exist $\delta,\alpha>0$ and a non-
negative integer $c$, so that there exists an explicit construction of an
infinite family $\\{H_{n}\\}_{n}$ of graphs, where $H_{n}$ is a $c$-left
regular bipartite graph with at least $n$ left vertices and $\beta n$ right
vertices that is a $(\delta,\alpha)$-unique neighbor expander.

In our second construction, given in Section 4, we use as an outer graph a
biregular $(\delta,\alpha)$-combinatorial expander for some constant
$\delta,\alpha>0$, and of sufficiently small imbalance $|R|/|L|$. We show that
this choice leads to an explicit construction of arbitrarily unbalanced unique
neighbor expanders with _roughly the same expansion_.

######  Theorem 1.3.

For any constant $\varepsilon,\alpha>0$, $\beta\in(0,1]$, and non-negative
integer $d$, there exist $\mu>0$ and a non-negative integer $c$ so that the
following holds. Suppose that there exists an explicit construction of an
infinite family of graphs $\\{G_{n}\\}_{n}$, where each $G_{n}$ is a
$(d,d/\mu)$-regular bipartite graph with $n$ left vertices that is a
$(\delta,\alpha)$-combinatorial expander. Then there exists an explicit
construction of an infinite family of graphs $\\{H_{n}\\}_{n}$, where each
$H_{n}$ is a $c$-left regular graph with $n$ left vertices and $\beta n$ right
vertices that is a $(\delta,(1-\varepsilon)\alpha)$-unique neighbor expander.

The above theorem can be viewed as an extension of the simple transformation
from combinatorial to unique neighbor expanders, given by Fact 1.1, to the
regime of $\alpha<\frac{1}{2}$.

As pointed out already by Sipser and Spielman, one can explicitly construct
biregular $(\delta,\alpha)$-combinatorial expanders for some constant
$\delta,\alpha>0$, and an arbitrarily small imbalance $|R|/|L|$, by taking the
edge-vertex incidence graph of a spectral expander of mild expansion, in which
case our second construction reduces to our first one (though the analysis is
a bit different). Beyond that, we are only aware of more sophisticated
constructions of lossless combinatorial expanders [CRVW02, CRT23, Gol23],
which to the best of our knowledge, are not biregular. Theorem 1.3 above
motivates the search for other simple constructions of biregular combinatorial
expanders, as these will also lead to simple constructions of unique neighbor
expanders of roughly the same expansion.

##  2 Preliminaries

In this section, we first provide the formal definitions of the types of
expanders that will shall consider in this work: spectral, combinatorial, and
unique neighbor expanders, and state known constructions of such graphs that
we shall use in our constructions. Then we formally define the routed product
that will be used for composing these expanders. See [HLW06] for an extensive
survey of expander graphs and their applications in theoretical computer
science.

###  2.1 Spectral expander

We start with the definition of a spectral expander, which is a (non-
bipartite) regular graph with bounded second eigenvalue.

######  Definition 2.1 (Spectral expander).

We say that a $d$-regular graph $G$ on $n$ vertices is a $\lambda$-_(spectral)
expander_ if $\max\\{|\lambda_{i}|,\lambda_{i}\neq\pm d\\}\leq\lambda$, where
$d=\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}$ are the eigenvalues of
the adjacency matrix of $G$.

For a graph $G=(V,E)$, and subsets $S,T\subseteq V$, we let $E(S,T)$ denote
the set of edges with one endpoint in $S$ and another endpoint in $T$, and we
let $|E(S,T)|$ denote the number of these edges, with the edges in $(S\cap
T)\times(S\cap T)$ counted twice. A commonly used property of spectral
expanders (and the only property of spectral expanders we shall use) is given
by the _expander mixing lemma_ of Alon and Chung [AC06]. This lemma says that
for a $d$-regular graph $G=(V,E)$, and for any pair of subsets $S,T\subseteq
V$, $|E(S,T)|$ is roughly equal the expected number of edges between $S$ and
$T$ in a random $d$-regular graph.

######  Theorem 2.2 (Expander Mixing Lemma, [AC06]).

Suppose that $G=(V,E)$ is a $d$-regular graph that is a $\lambda$-spectral
expander. Then for any pair of subsets $S,T\subseteq V$,

$\left|E(S,T)-\frac{d}{n}|S||T|\right|\leq\lambda\sqrt{|S||T|}.$

For our construction, we shall only need explicit constructions of infinite
families of $d$-regular graphs which are $(\delta d)$-expanders for an
arbitrarily small constant $\delta>0$, and an arbitrarily large degree $d$.
Such graphs can be obtained for example by taking graph powers of an infinite
family of $d$-regular $(\delta d)$-spectral expanders for some fixed non-
negative integer $d$ and fixed $\delta>0$ (for example those of Gabber and
Galil [GG81]), or, alternatively, using (a simple version of) the zig-zag
product [RVW00] (see also the survey [Vad12], Section 4.3).

######  Theorem 2.3 (Explicit spectral expanders).

For any $\delta>0$ and non-negative integer $d_{0}$, there exists a non-
negative integer $d\geq d_{0}$ so that there exists an explicit construction
of an infinite family $\\{G_{n}\\}_{n}$ of graphs, where $G_{n}$ is a
$d$-regular graph on $n$ vertices that is a $(\delta d)$-spectral expander.

To turn the above (non-bipartite) spectral expanders into bipartite graphs, we
shall consider the _edge-vertex incidence graph_ , defined as follows.

######  Definition 2.4 (Edge-vertex incidence graph).

The _edge-vertex incidence graph_ of a graph $G=(V,E)$ is the bipartite graph
$G^{\prime}=(L\cup R,E^{\prime})$, where $L=E$, $R=V$, and $(e,v)\in
E^{\prime}$ if $v$ is one of the endpoints of $e$ in $G$.

###  2.2 Combinatorial expander

A combinatorial expander is a graph, where any not too large subset has many
neighbors. In this work, we will only consider the bipartite one-sided version
of such expanders, where only left subsets expand.

We say that a bipartite graph $G=(L\cup R,E)$ is $d$-_left regular_ if
$\deg(v)=d$ for any $v\in L$, and we say that $G$ is ($d_{1},d_{2}$)-_regular_
if $\deg(v)=d_{1}$ for any $v\in L$ and $\deg(v)=d_{2}$ for any $v\in R$. We
say that $G$ is _$\beta$ -unbalanced_ if $|R|\leq\beta|L|$. For a vertex $v\in
L\cup R$, let $\Gamma_{G}(v)$ denote the set of vertices adjacent to $v$, and
for a subset $S\subseteq L$, let $\Gamma_{G}(S)$ denote the set of vertices
adjacent to some vertex in $S$, i.e., $\Gamma_{G}(S)=\bigcup_{v\in
S}\Gamma_{G}(v)$. We shall sometimes omit the subscript $G$ if the graph $G$
is clear from the context.

######  Definition 2.5 (Combinatorial expander).

We say that a $d$-left regular bipartite graph $G=(L\cup R,E)$ is a
$(\delta,\alpha)$-_(combinatorial) expander_ if $|\Gamma(S)|\geq\alpha d|S|$
for any non-empty subset $S\subseteq L$ with $|S|<\delta|L|$.

For our construction, we shall only need explicit constructions of infinite
families of $\beta$-unbalanced $(\delta,\alpha)$-expanders for some fixed
constants $\delta,\alpha>0$, and an arbitrarily small constant $\beta>0$. Such
constructions can be obtained for example by taking the edge-vertex incidence
graph of the spectral expanders given in Theorem 2.3 [SS96].

###  2.3 Unique neighbor expanders

A unique neighbor expander is a strengthening of a combinatorial expander,
where any not too large subset has many _unique_ neighbors. Once more, we will
only consider the bipartite one-sided version of such expanders.

Let $G=(L\cup R,E)$ be a bipartite graph. We say that a vertex $v\in R$ is a
_unique neighbor_ of a subset $S\subseteq L$ if $v$ is adjacent to exactly one
vertex in $S$, and for a subset $S\subseteq L$, we let
$\Gamma^{\mathrm{uni}}_{G}(S)$ denote the subset of all vertices $v\in R$
which are unique neighbors of $S$. Once more, we shall sometimes omit the
subscript $G$ if the graph $G$ is clear from the context.

######  Definition 2.6 (Unique neighbor (UN) expander).

We say that a $d$-left regular bipartite graph $G=(L\cup R,E)$ is a
$\delta$-_unique neighbor_ (UN) _expander_ if
$\Gamma^{\mathrm{uni}}(S)\neq\emptyset$ for any non-empty subset $S\subseteq
L$ with $|S|<\delta|L|$. We say that $G$ is a $(\delta,\alpha)$-_unique
neighbor_ (UN) _expander_ if $|\Gamma^{\mathrm{uni}}(S)|\geq\alpha d|S|$ for
any non-empty subset $S\subseteq L$ with $|S|<\delta|L|$.

It follows by definition, that any $(\delta,\alpha)$-UN expander is also a
$(\delta,\alpha)$-combinatorial expander. Conversely, it is not hard to show
that any $(\delta,1-\varepsilon)$-combinatorial expander is also a
$(\delta,1-2\varepsilon)$-UN expander. Note however that this latter
implication is only meaningful when $\varepsilon<\frac{1}{2}$.

For our construction, we shall need (possibly non-explicit) arbitrarily
unbalanced unique neighbor expanders. Such graphs (even with expansion
arbitrarily close to $1$) can be shown to exist using the probabilistic method
by (see e.g., [GRS], Lemmas 11.2.5).

######  Lemma 2.7 (Non-explicit unique neighbor expanders).

For any $\varepsilon>0$ and $\beta\in(0,1]$, there exist $\delta>0$ and non-
negative integers $d$ and $n_{0}$, so that for all $n\geq n_{0}$, there exists
a $d$-left regular $\beta$-unbalanced bipartite graph $G_{n}$ with $n$ left
vertices that is a $(\delta,1-\varepsilon)$-UN expander.

###  2.4 The routed product

In this work, we will obtain explicit constructions of unique neighbor
expanders by combining "outer graphs" which are either the edge-vertex
incidence graph of explicit spectral expanders, or explicit combinatorial
expanders, with "inner graphs" which are non-explicit unique neighbor
expanders, via the _routed product_ , defined as follows (this product first
appeared implicitly in [AC02], and formally defined later in [AD23]).

######  Definition 2.8 (The routed product [AC02, AD23]).

Let $G=(L\cup R,E)$ be an _outer_ $(d_{1},d_{2})$-regular bipartite graph, and
let $G^{\prime}=(L^{\prime}\cup R^{\prime},E^{\prime})$ be an _inner_
$d^{\prime}$-left regular bipartite graph with $L^{\prime}=[d_{2}]$.
Furthermore, for any $v\in R$, assume an ordering on the $d_{2}$ edges of $E$
incident to $v$ in $G$.

The _routed product_ $G\circ G^{\prime}$ is the bipartite graph $G\circ
G^{\prime}:=(L^{\prime\prime}\cup R^{\prime\prime},E^{\prime\prime})$, where
$L^{\prime\prime}=L$, $R^{\prime\prime}=R\times R^{\prime}$, and
$(u,(v,v^{\prime}))\in E^{\prime\prime}$ if there exists $i\in[d_{2}]$ so that
$(u,v)$ is the $i$-th edge incident to $v$ in $G$ and $(i,v^{\prime})\in
E^{\prime}$.

It follows by definition, that $G\circ G^{\prime}$ is $(d_{1}\cdot
d^{\prime})$-left regular, and that if $G^{\prime}$ is
$\beta^{\prime}$-unbalanced, then $G\circ G^{\prime}$ is
$\tilde{\beta}$-unbalanced for

$\tilde{\beta}=\frac{|R|\cdot|R^{\prime}|}{|L|}=\frac{|R|\cdot|R^{\prime}|}{d_{2}\cdot|R|/d_{1}}=\frac{d_{1}\cdot|R^{\prime}|}{|L^{\prime}|}=d_{1}\cdot\beta^{\prime}.$

##  3 Unique Neighbor Expanders from Spectral Expanders

In this section, we will show how to obtain a simple explicit construction of
unique neighbor expanders by combining "outer graphs" which are the edge-
vertex incidence graph of explicit spectral expanders with "inner graphs"
which are non-explicit unique neighbor expanders via the routed product.

To this end, we first show in Section 3.1, as a warmup, how to obtain explicit
unique neighbor expanders that only guarantee the existence of a _single_
unique neighbor for any not too large left subset, using the analysis of
error-correcting codes that is implicit in [SS96]. Then in Section 3.2, we
show a slight strengthening of the analysis that guarantees a _constant
fraction_ of unique neighbors. Finally, in Section 3.3, we instantiate our
transformation with the explicit spectral expanders given by Theorem 2.3, and
the non-explicit unique neighbor expanders given by Lemma 2.7, to obtain
explicit unique neighbor expanders.

###  3.1 One unique neighbor

The following lemma says that the routed product of an outer edge-vertex
incidence graph of a spectral expander with an inner unique neighbor expander
yields a unique neighbor expander, where both unique neighbor expanders
guarantee the existence of only a _single_ unique neighbor for any not too
large left subset.

######  Lemma 3.1.

Suppose that $G=(L\cup R,E)$ is the edge-vertex incidence graph of a
$d$-regular graph that is a $\lambda$-spectral expander, and that
$G^{\prime}=(L^{\prime}\cup R^{\prime},E^{\prime})$ is a $d^{\prime}$-left
regular bipartite graph that is a $\delta^{\prime}$-UN expander with
$L^{\prime}=[d]$. Then $G\circ G^{\prime}=(L^{\prime\prime}\cup
R^{\prime\prime},E^{\prime\prime})$ is a
$(\delta^{\prime}(\delta^{\prime}-\frac{\lambda}{d}))$-UN expander.

The following lemma is implicit in the analysis of error-correcting codes of
[SS96]. Its proof is an easy consequence of the expander mixing lemma (Theorem
2.2). For completeness, and since in the next section we shall need a slight
strengthening of this lemma, we provide a full proof of this lemma below.

######  Lemma 3.2.

Let $G=(V,E)$ be a $d$-regular graph that is a $\lambda$-spectral expander,
and let $S\subseteq E$ be a subset of edges in $G$. Suppose that for any $v\in
V$ that is incident to some edge in $S$, it holds that $v$ is incident to at
least $\delta d$ edges in $S$. Then
$|S|\geq\delta(\delta-\frac{\lambda}{d})|E|$.

###### Proof.

Let $U\subseteq V$ be the subset of vertices in $G$ which are incident to some
edge in $S$. Then by assumption, each vertex of $U$ is incident to at least
$\delta d$ other vertices of $U$, and consequently we have that
$|E(U,U)|\geq\delta d|U|$ (recall that by definition, each edge with both
endpoints in $U$ is counted twice in $|E(U,U)|$). On the other hand, by the
expander mixing lemma (Theorem 2.2), we have that
$|E(U,U)|\leq\frac{d}{n}|U|^{2}+\lambda|U|$. Combining these two inequalities
gives that $|U|\geq(\delta-\frac{\lambda}{d})n$. But by assumption that each
vertex in $U$ is incident to at least $\delta d$ edges in $S$, this implies in
turn that

$|S|\geq\frac{1}{2}\delta
d|U|\geq\delta\left(\delta-\frac{\lambda}{d}\right)\cdot\frac{dn}{2}=\delta\left(\delta-\frac{\lambda}{d}\right)|E|.$

∎

By the definition of the edge-vertex incidence graph, the above lemma can be
equivalently stated as follows.

######  Lemma 3.3 (Equivalent statement of Lemma 3.2).

Let $G=(L\cup R,E)$ be the edge-vertex incidence graph of a $d$-regular graph
that is a $\lambda$-spectral expander, and let $S\subseteq L$ be a subset of
left vertices in $G$. Suppose that $|\Gamma(v)\cap S|\geq\delta d$ for any
$v\in\Gamma(S)$. Then $|S|\geq\delta(\delta-\frac{\lambda}{d})|L|$.

We now proceed to the proof of Lemma 3.1, based on the above lemma.

###### Proof of Lemma 3.1.

Let $S\subseteq L^{\prime\prime}=L$ be a subset of left vertices in $G\circ
G^{\prime}$ of size
$|S|<\delta^{\prime}(\delta^{\prime}-\frac{\lambda}{d})|L^{\prime\prime}|=\delta^{\prime}(\delta^{\prime}-\frac{\lambda}{d})|L|$.
Then by Lemma 3.3, there must exist a vertex $v\in\Gamma_{G}(S)$ so that
$|\Gamma_{G}(v)\cap S|<\delta^{\prime}d$.

Let $I\subseteq[d]$ be the subset which contains all indices of edges in
$\Gamma_{G}(v)$ which are contained in $S$. Then $I$ is a non-empty subset
satisfying that $|I|<\delta^{\prime}d=\delta^{\prime}|L^{\prime}|$, and since
$G^{\prime}$ is a $\delta^{\prime}$-UN expander, there exists a vertex
$v^{\prime}\in R^{\prime}$ which is a unique neighbor of $I$ in $G^{\prime}$.
By the definition of the routed product, this implies in turn that
$(v,v^{\prime})$ is a unique neighbor of $S$ in $G\circ G^{\prime}$. ∎

###  3.2 Constant fraction of unique neighbors

The following lemma says that the routed product of an outer edge-vertex
incidence graph of a spectral expander with an inner unique neighbor expander
yields a unique neighbor expander, where now both unique neighbor expanders
guarantee the existence of a _constant fraction_ of unique neighbors for any
not too large left subset.

######  Lemma 3.4.

Suppose that $G=(L\cup R,E)$ is the edge-vertex incidence graph of a
$d$-regular graph that is a $\lambda$-spectral expander, and that
$G^{\prime}=(L^{\prime}\cup R^{\prime},E^{\prime})$ is a $d^{\prime}$-left
regular bipartite graph that is a $(\delta^{\prime},\alpha^{\prime})$-UN
expander with $L^{\prime}=[d]$. Then for any $\gamma\in(0,1)$, $G\circ
G^{\prime}=(L^{\prime\prime}\cup R^{\prime\prime},E^{\prime\prime})$ is a
$(\gamma\delta^{\prime}(\gamma\delta^{\prime}-\frac{\lambda}{d}),\frac{(1-\gamma)\alpha^{\prime}}{d})$-UN
expander.

To prove the above lemma we shall need the following quantitative version of
Lemma 3.2.

######  Lemma 3.5.

Let $G=(V,E)$ be a $d$-regular graph that is a $\lambda$-spectral expander,
let $S\subseteq E$ be a subset of edges in $G$, and let $U\subseteq V$ be the
subset of vertices in $G$ which are incident to some edge in $S$. Suppose that
at least a $\gamma$-fraction of the vertices of $U$ are incident to at least
$\delta d$ edges in $S$. Then
$|S|\geq\gamma\delta(\gamma\delta-\frac{\lambda}{d})|E|$.

###### Proof.

By assumption, at least a $\gamma$-fraction of the vertices of $U$ are
incident to at least $\delta d$ other vertices in $U$, and consequently we
have that $|E(U,U)|\geq\gamma\delta d|U|$. On the other hand, by the expander
mixing lemma (Theorem 2.2), we have that
$|E(U,U)|\leq\frac{d}{n}|U|^{2}+\lambda|U|$. Combining these two inequalities
gives that $|U|\geq(\gamma\delta-\frac{\lambda}{d})n$. But by assumption that
at least a $\gamma$-fraction of the vertices of $U$ are incident to at least
$\delta d$ edges in $S$, this implies in turn that

$|S|\geq\frac{1}{2}\gamma\delta
d|U|\geq\gamma\delta\left(\gamma\delta-\frac{\lambda}{d}\right)\frac{dn}{2}=\gamma\delta\left(\gamma\delta-\frac{\lambda}{d}\right)|E|.$

∎

As before, by the definition of the edge-vertex incidence graph, the above
lemma can be equivalently stated as follows.

######  Lemma 3.6 (Equivalent statement of Lemma 3.5).

Let $G=(L\cup R,E)$ be the edge-vertex incidence graph of a $d$-regular graph
that is a $\lambda$-spectral expander, and let $S\subseteq L$ be a subset of
left vertices in $G$. Suppose that $|\Gamma(v)\cap S|\geq\delta d$ for at
least a $\gamma$-fraction of the vertices in $\Gamma(S)$. Then
$|S|\geq\gamma\delta(\gamma\delta-\frac{\lambda}{d})|L|$.

We now proceed to the proof of Lemma 3.4, based on the above lemma.

###### Proof of Lemma 3.4.

Let $S\subseteq L^{\prime\prime}=L$ be a subset of left vertices in $G\circ
G^{\prime}$ of size
$|S|<\gamma\delta^{\prime}(\gamma\delta^{\prime}-\frac{\lambda}{d})|L^{\prime\prime}|=\gamma\delta^{\prime}(\gamma\delta^{\prime}-\frac{\lambda}{d})|L|$.
Then by Lemma 3.6, $|\Gamma_{G}(v)\cap S|<\delta^{\prime}d$ for at least a
$(1-\gamma)$-fraction of the vertices in $\Gamma_{G}(S)$.

Let $v\in\Gamma_{G}(S)$ be a vertex which satisfies that $|\Gamma_{G}(v)\cap
S|<\delta^{\prime}d$. As in the proof of Lemma 3.1, let $I\subseteq[d]$ be the
subset which contains all indices of edges in $\Gamma_{G}(v)$ which are
contained in $S$. Then $I$ is a non-empty subset satisfying that
$|I|<\delta^{\prime}d=\delta^{\prime}|L^{\prime}|$, and since $G^{\prime}$ is
a $(\delta^{\prime},\alpha^{\prime})$-UN expander, at least
$\alpha^{\prime}d^{\prime}$ vertices $v^{\prime}\in R^{\prime}$ are unique
neighbors of $I$ in $G^{\prime}$. By the definition of the routed product,
this implies in turn that $(v,v^{\prime})$ is a unique neighbor of $S$ in
$G\circ G^{\prime}$ for at least $\alpha^{\prime}d^{\prime}$ vertices
$v^{\prime}\in R^{\prime}$.

Overall, we get that the number of unique neighbors of $S$ in $G\circ
G^{\prime}$ is at least

$|\Gamma^{\mathrm{uni}}_{G\circ
G^{\prime}}(S)|\geq\alpha^{\prime}d^{\prime}(1-\gamma)|\Gamma_{G}(S)|\geq\alpha^{\prime}d^{\prime}(1-\gamma)\frac{2|S|}{d}=\frac{(1-\gamma)\alpha^{\prime}}{d}\cdot(2d^{\prime})|S|,$

where the bound $|\Gamma_{G}(S)|\geq\frac{2|S|}{d}$ follows since $G$ is
$(2,d)$-regular. The conclusion follows by recalling that by the definition of
the routed product, $G\circ G^{\prime}$ is $(2d^{\prime})$-left regular. ∎

###  3.3 Instantiation

Applying Lemma 3.4 with the outer graph being the explicit spectral expander
given by Theorem 2.3, and the inner graph being the non-explicit unique
neighbor expander given by Lemma 2.7, gives Theorem 1.2, restated below, which
gives an explicit construction of a unique neighbor expander.

See 1.2

###### Proof.

Let $\delta^{\prime}>0$ and $d^{\prime},n^{\prime}_{0}$ be the constant and
non-negative integers guaranteed by Lemma 2.7 for
$\varepsilon^{\prime}=\frac{1}{2}$ and $\beta^{\prime}=\frac{\beta}{2}$. Let
$d\geq d_{0}$ be the non-negative integer guaranteed by Theorem 2.3 for
$\frac{\delta^{\prime}}{4}$ and $d_{0}=n^{\prime}_{0}$. Let $G^{\prime}_{d}$
be the $d^{\prime}$-left regular $\frac{\beta}{2}$-unbalanced bipartite graph
with $d$ left vertices that is a $(\delta^{\prime},\frac{1}{2})$-UN expander,
guaranteed by Lemma 2.7. Note that $G^{\prime}_{d}$ can be found in constant
time via brute force search. Let $\\{G_{n}\\}_{n}$ be the explicit infinite
family of graphs, where each $G_{n}$ is a $d$-regular graph on $n$ vertices
that is a $(\frac{\delta^{\prime}}{4}\cdot d)$-spectral expander, guaranteed
by Theorem 2.3.

Let $H_{n}:=I(G_{n})\circ G^{\prime}_{d}$, where $I(G_{n})$ is the edge-vertex
incidence graph of $G_{n}$. Then by the definition of the routed product,
$H_{n}$ is a $(2d^{\prime})$-left regular $\beta$-unbalanced bipartite graph
with $\frac{dn}{2}$ left vertices. Moreover, applying Lemma 3.4 with
$\gamma=\frac{1}{2}$ gives that $H_{n}$ is a
$(\frac{(\delta^{\prime})^{2}}{8},\frac{1}{4d})$-UN expander. So the theorem
holds with $c=2d^{\prime}$, $\delta=\frac{(\delta^{\prime})^{2}}{8}$, and
$\alpha=\frac{1}{4d}$, which are all constant depending only on $\beta$. ∎

##  4 Unique Neighbor Expanders from Combinatorial Expanders

In this section we show that composing an outer explicit combinatorial
expander with an inner non-explicit unique neighbor expander via the routed
product gives an explicit unique neighbor expander with _roughly the same
expansion_ as the outer combinatorial expander.

As in the previous section, we first show in Section 4.1, as a warmup, how to
obtain explicit unique neighbor expanders that only guarantee the existence of
a single unique neighbor, using the analysis of error-correcting codes that is
implicit in [SS96]. Then in Section 4.2, we show how to extend the analysis to
obtain a constant fraction of unique neighbors. Finally, in Section 4.3, we
instantiate our transformation with the non-explicit unique neighbor expanders
given by Lemma 2.7 to obtain the final transformation.

###  4.1 One unique neighbor

The following lemma says that the routed product of an outer combinatorial
expander with an inner unique neighbor expander yields a unique neighbor
expander, where both unique neighbor expanders guarantee the existence of only
a _single_ unique neighbor for any not too large left subset.

######  Lemma 4.1.

Suppose that $G=(L\cup R,E)$ is a $(d_{1},d_{2})$-regular bipartite graph that
is a $(\delta,\alpha)$-expander, and that $G^{\prime}=(L^{\prime}\cup
R^{\prime},E^{\prime})$ is a $d^{\prime}$-left regular bipartite graph that is
a $\frac{1}{\alpha d_{2}}$-UN expander with $L^{\prime}=[d_{2}]$. Then $G\circ
G^{\prime}=(L^{\prime\prime}\cup R^{\prime\prime},E^{\prime\prime})$ is a
$\delta$-UN expander.

The following simple lemma is implicit in the analysis of error-correcting
codes of [SS96]. For completeness, and since in the next section we shall need
a slight strengthening of this lemma, we provide a full proof of this lemma
below.

######  Lemma 4.2.

Let $G=(L\cup R,E)$ be a $(d_{1},d_{2})$-regular bipartite graph that is a
$(\delta,\alpha)$-expander, and let $S\subseteq L$ be a subset of left
vertices in $G$. Suppose that $|\Gamma(v)\cap S|>\frac{1}{\alpha}$ for any
$v\in\Gamma(S)$. Then $|S|\geq\delta|L|$.

###### Proof.

By assumption that $|\Gamma(v)\cap S|>\frac{1}{\alpha}$ for any
$v\in\Gamma(S)$, we have that $|E(S,\Gamma(S))|>\frac{1}{\alpha}|\Gamma(S)|$.
On the other hand, since $G$ is $(d_{1},d_{2})$-regular, we have that
$|E(S,\Gamma(S))|=d_{1}|S|$. Combining these two inequalities gives that
$|\Gamma(S)|<\alpha d_{1}|S|$. By assumption that $G$ is a
$(\delta,\alpha)$-expander, this implies in turn that $|S|\geq\delta|L|$. ∎

We now proceed to the proof of Lemma 4.1, based on the above lemma.

###### Proof of Lemma 4.1.

Let $S\subseteq L^{\prime\prime}=L$ be a subset of left vertices in $G\circ
G^{\prime}$ of size $|S|<\delta|L^{\prime\prime}|=\delta|L|$. Then by Lemma
4.2, there must exist a vertex $v\in\Gamma_{G}(S)$ so that $|\Gamma_{G}(v)\cap
S|\leq\frac{1}{\alpha}$.

Let $I\subseteq[d_{2}]$ be the subset which contains all indices of edges in
$\Gamma_{G}(v)$ which are contained in $S$. Then $I$ is a non-empty subset
satisfying that $|I|<\frac{1}{\alpha}=\frac{1}{\alpha
d_{2}}\cdot|L^{\prime}|$, and since $G^{\prime}$ is a $(\frac{1}{\alpha
d_{2}})$-UN expander, there exists a vertex $v^{\prime}\in R^{\prime}$ which
is a unique neighbor of $I$ in $G^{\prime}$. By the definition of the routed
product, this implies in turn that $(v,v^{\prime})$ is a unique neighbor of
$S$ in $G\circ G^{\prime}$. ∎

###  4.2 Constant fraction of unique neighbors

The following lemma says that the routed product of an outer combinatorial
expander with an inner unique neighbor expander yields a unique neighbor
expander, where now both unique neighbor expanders guarantee the existence of
a _constant fraction_ of unique neighbors for any not too large left subset.

######  Lemma 4.3.

The following holds for any $\gamma\in(0,1)$. Suppose that $G=(L\cup R,E)$ is
a $(d_{1},d_{2})$-regular bipartite graph that is a
$(\delta,\alpha)$-expander, and that $G^{\prime}=(L^{\prime}\cup
R^{\prime},E^{\prime})$ is a $d^{\prime}$-left regular bipartite graph that is
a $(\frac{1}{\gamma\alpha d_{2}},\alpha^{\prime})$-UN expander with
$L^{\prime}=[d_{2}]$. Then $G\circ G^{\prime}=(L^{\prime\prime}\cup
R^{\prime\prime},E^{\prime\prime})$ is a
$(\delta,(1-\gamma)\alpha^{\prime}\alpha)$-UN expander.

To prove the above lemma we shall need the following quantitative version of
Lemma 4.2.

######  Lemma 4.4.

Let $G=(L\cup R,E)$ be a $(d_{1},d_{2})$-regular bipartite graph that is a
$(\delta,\alpha)$-expander, and let $S\subseteq L$ be a subset of left
vertices in $G$. Suppose that $|\Gamma(v)\cap S|>\frac{1}{\gamma\alpha}$ for
at least a $\gamma$-fraction of the vertices in $\Gamma(S)$. Then
$|S|\geq\delta|L|$.

###### Proof.

By assumption that $|\Gamma(v)\cap S|>\frac{1}{\gamma\alpha}$ for at least a
$\gamma$-fraction of the vertices in $\Gamma(S)$, we have that
$|E(S,\Gamma(S))|>\frac{1}{\alpha}|\Gamma(S)|$. On the other hand, since $G$
is $(d_{1},d_{2})$-regular, we have that $|E(S,\Gamma(S))|=d_{1}|S|$.
Combining these two inequalities gives that $|\Gamma(S)|<\alpha d_{1}|S|$. By
assumption that $G$ is a $(\delta,\alpha)$-expander, this implies in turn that
$|S|\geq\delta|L|$. ∎

We now proceed to the proof of Lemma 4.3, based on the above lemma.

###### Proof of Lemma 4.3.

Let $S\subseteq L^{\prime\prime}=L$ be a subset of left vertices in $G\circ
G^{\prime}$ of size $|S|<\delta|L^{\prime\prime}|=\delta|L|$. Then by Lemma
4.4, $|\Gamma_{G}(v)\cap S|<\frac{1}{\gamma\alpha}$ for at least a
$(1-\gamma)$-fraction of the vertices in $\Gamma_{G}(S)$.

Let $v\in\Gamma_{G}(S)$ be a vertex which satisfies that $|\Gamma_{G}(v)\cap
S|<\frac{1}{\gamma\alpha}$. As in the proof of Lemma 4.1, let
$I\subseteq[d_{2}]$ denote the subset which contains all indices of edges in
$\Gamma_{G}(v)$ which are contained in $S$. Then $I$ is a non-empty subset
satisfying that $|I|<\frac{1}{\gamma\alpha}=\frac{1}{\gamma\alpha
d_{2}}\cdot|L^{\prime}|$, and since $G^{\prime}$ is a $(\frac{1}{\gamma\alpha
d_{2}},\alpha^{\prime})$-UN expander, at least $\alpha^{\prime}d^{\prime}$
vertices $v^{\prime}\in R^{\prime}$ are unique neighbors of $I$ in
$G^{\prime}$. By the definition of the routed product, this implies in turn
that $(v,v^{\prime})$ is a unique neighbor of $S$ in $G\circ G^{\prime}$ for
at least $\alpha^{\prime}d^{\prime}$ vertices $v^{\prime}\in R^{\prime}$.

Overall, we get that the number of unique neighbors of $S$ in $G\circ
G^{\prime}$ is at least

$|\Gamma^{\mathrm{uni}}_{G\circ
G^{\prime}}(S)|\geq\alpha^{\prime}d^{\prime}(1-\gamma)|\Gamma_{G}(S)|\geq\alpha^{\prime}d^{\prime}(1-\gamma)\cdot(\alpha
d_{1}|S|)=(1-\gamma)\alpha^{\prime}\alpha\cdot(d_{1}\cdot d^{\prime})|S|,$

where the bound $|\Gamma_{G}(S)|\geq\alpha d_{1}|S|$ follows since $G$ is a
$(\delta,\alpha)$-expander. The conclusion follows by recalling that by the
definition of the routed product, $G\circ G^{\prime}$ is $(d_{1}\cdot
d^{\prime})$-left regular. ∎

###  4.3 Instantiation

Applying Lemma 4.3 with the inner graph being the non-explicit unique neighbor
expander given by Lemma 2.7, gives Theorem 1.3, restated below, which shows
how to transform combinatorial expanders into unique neighbor expanders with
roughly the same expansion.

See 1.3

###### Proof.

Let $\delta^{\prime}>0$ and $d^{\prime},n^{\prime}_{0}$ be the constant and
non-negative integers guaranteed by Lemma 2.7 for
$\varepsilon^{\prime}:=\frac{\varepsilon}{2}$ and
$\beta^{\prime}:=\frac{\beta}{d}$. Let
$\mu:=\min\\{\frac{\varepsilon\alpha\delta^{\prime}d}{2},\frac{1}{n^{\prime}_{0}}\\}$.
Let $G^{\prime}_{d/\mu}$ be the $d^{\prime}$-left regular
$\frac{\beta}{d}$-unbalanced bipartite graph with $d/\mu$ left vertices that
is a $(\delta^{\prime},1-\frac{\varepsilon}{2})$-UN expander, guaranteed by
Lemma 2.7. Note that $G^{\prime}_{d}$ can be found in constant time via brute
force search.

Let $H_{n}:=G_{n}\circ G^{\prime}_{d/\mu}$. Then by the definition of the
routed product, $H_{n}$ is a $(d\cdot d^{\prime})$-left regular
$\beta$-unbalanced bipartite graph with $n$ left vertices. Let
$\gamma:=\frac{\varepsilon}{2}$, and note that by our choice of $\mu$ we have
that $\frac{1}{\gamma\alpha(d/\mu)}\leq\delta^{\prime}$. Therefore, applying
Lemma 4.3 with this choice of $\gamma$ gives that $H_{n}$ is a
$(\delta,(1-\varepsilon)\alpha)$-UN expander. ∎

#### Acknowledgement

We thank Ronen Shaltiel for a discussion about existing constructions of
bipartite expander graphs.

## References

  * [AC02] Noga Alon and Michael Capalbo.  Explicit unique-neighbor expanders.  In proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), page 73. IEEE Computer Society, 2002.
  * [AC06] Noga Alon and Fan R. K. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Mathematics, 306(10-11):1068–1071, 2006.
  * [AD23] Ron Asherov and Irit Dinur.  Bipartite unique-neighbour expanders via ramanujan graphs.  CoRR, abs/2301.03072, 2023.
  * [ALM96] Sanjeev Arora, Frank Thomson Leighton, and Bruce M. Maggs.  On-line algorithms for path selection in a nonblocking network.  SIAM Journal on Computing, 25(3):600–625, 1996.
  * [BV09] Eli Ben-Sasson and Michael Viderman.  Tensor products of weakly smooth codes are robust.  Theory of Computing, 5(1):239–255, 2009.
  * [CRT23] Itay Cohen, Roy Roth, and Amnon Ta-Shma.  HDX condensers.  Electronic Colloquium on Computational Complexity, TR23-090, 2023\.
  * [CRVW02] Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson.  Randomness conductors and constant-degree lossless expanders.  In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 659–668. ACM Press, 2002.
  * [DSW06] Irit Dinur, Madhu Sudan, and Avi Wigderson.  Robust local testability of tensor products of LDPC codes.  In proceedings of the 9th International Workshop on Randomization and Computation (RANDOM), pages 304–315. Springer, 2006.
  * [GG81] Ofer Gabber and Zvi Galil.  Explicit constructions of linear-sized superconcentrators.  Journal of Computer and System Sciences, 22(3):407–420, 1981.
  * [Gol23] Louis Golowich.  New explicit constant-degree lossless expanders.  CoRR, abs/2306.07551, 2023.
  * [GRS] Essential coding theory.  https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/web-coding-book.pdf.  Accessed: 2023-09-08.
  * [HLW06] Shlomo Hoory, Nati Linial, and Avi Wigderson.  Expander graphs and their applications.  Bulletin of AMS, 43(4):439–561, 2006.
  * [HMMP23] Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, and Pedro Paredes.  Explicit two-sided unique-neighbor expanders.  CoRR, abs/2302.01212, 2023.
  * [Pip96] Nicholas Pippenger.  Self-routing superconcentrators.  Journal of Computer and System Sciences, 52(1):53–60, 1996.
  * [PU89] David Peleg and Eli Upfal.  The token distribution problem.  SIAM Journal on Computing, 18(2):229–243, 1989.
  * [RVW00] Omer Reingold, Salil P. Vadhan, and Avi Wigderson.  Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors.  In proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 3–13. IEEE Computer Society, 2000.
  * [SS96] Michael Sipser and Daniel Spielman.  Expander codes.  IEEE Transactions on Information Theory, 42(6):1710–1722, 1996\.
  * [Tan81] R. Tanner.  A recursive approach to low complexity codes.  IEEE Transactions on Information Theory, 27(5):533–547, 1981.
  * [Vad12] Salil P. Vadhan.  Pseudorandomness.  Foundations and Trends in Theoretical Computer Science, 7(1-3):1–336, 2012.