# On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good
Codes

Andrew Drucker111Independent<EMAIL_ADDRESS>Yuan Li222School
of Computer Science, Fudan University. Email<EMAIL_ADDRESS>An earlier
version of this work appeared as Chapter 2 of the author’s Ph.D. thesis
[Li17]. Part of this work was done while the authors were affiliated with the
University of Chicago Computer Science Dept.

###### Abstract

Let $S_{d}(n)$ denote the minimum number of wires of a depth-$d$ (unbounded
fan-in) circuit encoding an error-correcting code
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with distance at least $4n$. Gál, Hansen,
Koucký, Pudlák, and Viola [IEEE Trans. Inform. Theory 59(10), 2013] proved
that $S_{d}(n)=\Theta_{d}(\lambda_{d}(n)\cdot n)$ for any fixed $d\geq 3$. By
improving their construction and analysis, we prove
$S_{d}(n)=O(\lambda_{d}(n)\cdot n)$. Letting $d=\alpha(n)$, a version of the
inverse Ackermann function, we obtain circuits of linear size. This depth
$\alpha(n)$ is the minimum possible to within an additive constant 2; we
credit the nearly-matching depth lower bound to Gál _et al._ , since it
directly follows their method (although not explicitly claimed or fully
verified in that work), and is obtained by making some constants explicit in a
graph-theoretic lemma of Pudlák [Combinatorica, 14(2), 1994], extending it to
super-constant depths.

We also study a subclass of MDS codes $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$
characterized by the Hamming-distance relation
$\operatorname{dist}(C(x),C(y))\geq m-\operatorname{dist}(x,y)+1$ for any
distinct $x,y\in\mathbb{F}^{n}$. (For linear codes this is equivalent to the
generator matrix being totally invertible.) We call these _superconcentrator-
induced codes_ , and we show their tight connection with superconcentrators.
Specifically, we observe that any linear or nonlinear circuit encoding a
superconcentrator-induced code must be a superconcentrator graph, and any
superconcentrator graph can be converted to a linear circuit, over a
sufficiently large field (exponential in the size of the graph), encoding a
superconcentrator-induced code.

Keywords: error-correcting codes, circuit complexity, superconcentrator.

##  1 Introduction

Understanding the computational complexity of _encoding_ error-correcting
codes is an important task in theoretical computer science. Complexity
measures of interest include time, space, and parallelism. Error-correcting
codes are indispensable as a tool in computer science. Highly efficient
encoding algorithms (or circuits) are desirable in settings studied by
theorists including zero-knowledge proofs [Gol+21], circuit lower bounds
[CT19], data structures for error-correcting codes [Vio19], pairwise-
independent hashing [Ish+08], and secret sharing [DI14]. Besides that, the
_existence_ of error-correcting codes with efficient encoding circuits sheds
light on the designing of practical error-correcting codes.

We consider codes with constant rate and constant relative distance, which are
called asymptotically good error-correcting codes or _good codes_ for short.
The complexity of encoding good codes has been studied before. Bazzi and
Mitter [BM05] proved that branching programs with linear time and sublinear
space cannot encode good codes. By using the sensitivity bounds [Bop97], one
can prove that $\mathsf{AC}^{0}$ circuits cannot encode good codes; Lovett and
Viola proved that $\mathsf{AC}^{0}$ circuits cannot sample good codes [LV11];
Beck, Impagliazzo and Lovett [BIL12] strengthened the result.

Dobrushin, Gelfand and Pinsker [DGP73] proved that there exist linear-size
circuits encoding good codes. Sipser and Spielman [Spi96, SS96] explicitly
constructed good codes that are encodable by bounded fanin circuits of depth
$O(\log n)$ and size $O(n)$, and decodable by circuits of size $O(n\log n)$.
For bounded fan-in, the depth $O(\log n)$ is obviously optimal. Henceforth,
unless otherwise stated, we consider circuits with unbounded fan-in, where the
size is measured by the number of _wires_ instead of gates.

Gál, Hansen, Koucký, Pudlák, and Viola [Gal+13] investigated the circuit
complexity of encoding good codes. Gál _et al._ constructed circuits
recursively and probabilistically, with clever recursive composition ideas,
which resemble the construction of superconcentrators in [Dol+83]. They also
proved size lower bounds for bounded depth, by showing that any circuit
encoding good codes must satisfy some superconcentrator-like properties; the
lower bound follows from the size bounds for a variant of bounded-depth
superconcentrators studied by Pudlák [Pud94]. Their construction’s wire upper
bounds are of form $O_{d}(n\cdot\lambda_{d}(n))$ (in our notation333Our
definition of $\lambda_{d}(n)$ follows Raz and Shpilka [RS03]. It is slightly
different from Gál _et al._ ’s. In [Gal+13], the function $\lambda_{i}(n)$ is
actually $\lambda_{2i}(n)$ in our notation.) and their lower bounds are of
form $\Omega_{d}(n\cdot\lambda_{d}(n))$, matching up to a multiplicative
constant $c_{d}$ for constant values $d$. They also proved that there exist
$O_{d}(n)$-size $O(\log\lambda_{d}(n))$-depth circuits encoding good codes.
Here $\lambda_{d}(n)$ are slowly growing inverse Ackermann-type functions,
e.g., $\lambda_{2}(n)=\Theta(\log n)$, $\lambda_{3}(n)=\Theta(\log\log n)$,
$\lambda_{4}(n)=\Theta(\log^{*}n)$.

Druk and Ishai [DI14] proposed a randomized construction of good codes meeting
the Gilbert-Varshamov bound, which can be encoded by linear-size logarithmic-
depth circuits (with bounded fan-in). Their construction is based on linear-
time computable pairwise independent hash functions [Ish+08].

Chen and Tell [CT19] constructed _explicit_ circuits of depth $d$ encoding
linear codes with constant relative distance and code rate
$\Omega\left(\frac{1}{\log n}\right)$ using $n^{1+2^{-\Omega(d)}}$ wires, for
every $d\geq 4$. They used these explicit circuits to prove bootstrapping
results for threshold circuits.

###  1.1 Background and results

To encode good error-correcting codes, linear size is obviously required. It
is natural to ask, what is the minimum depth required to encode goods using a
linear number of wires? This question is addressed, but not fully answered, by
the work of Gál _et al._ [Gal+13].

We show that one can non-explicitly encode error-correcting codes with
constant rate and constant relative distance using $O(n)$ wires, with depth at
most $\alpha(n)$, for sufficiently large $n$. Here, $\alpha(n)$ is a version
of the inverse Ackermann function. This is nearly optimal, by a lower bound of
$\alpha(n)-2$ that we credit to Gál _et al._ [Gal+13] as discussed below. Our
new upper bound states:

######  Theorem 1.1.

(Upper bound) Let $r\in(0,1)$ and $\delta\in(0,\frac{1}{2})$ such that
$r<1-h(\delta)$. For sufficiently large $n$ and for any $d\geq 3$, not
necessarily a constant, there exists a linear circuit
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{\lfloor\frac{n}{r}\rfloor}$ of size
$O_{r,\delta}(\lambda_{d}(n)\cdot n)$ and depth $d$ that encodes an error-
correcting code with relative distance $\geq\delta$. In particular, when
$d=\alpha(n)$, the circuit is of size $O_{r,\delta}(n)$.

Our upper bound improves the construction and the analysis by Gál _et al._
[Gal+13]. Specifically, let $S_{d}(n)$ denote the minimum size of a depth-$d$
linear circuit encoding a code $C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with
distance $4n$. Gál _et al._ proved that $S_{d}(n)=O_{d}(\lambda_{d}(n)\cdot
n)$, where the hidden constant in $O_{d}(\lambda_{d}(n)\cdot n)$ grows rapidly
as an Ackermann-type function (if one follows their arguments and expand the
computation straightforwardly in Lemma 26 in [Gal+13].) They also proved that,
for any _fixed_ $m$, when the depth $d=O(\log(\lambda_{m}(n)))$,
$S_{d}(n)=O_{m}(n)$. Their upper bound is strong, but suboptimal. Our main
technical contribution is to prove $S_{d}(n)=O(\lambda_{d}(n)\cdot n)$, where
the hidden constant is an absolute constant. Explaining how this improvement
is obtained is a bit technical, and defeered to the next subsection.

Turning to the lower bounds: we credit the lower bound in the result below to
Gál _et al._ (although it was not explicitly claimed or fully verified in that
work), since it is directly obtainable by their size lower-bound method and
the tool of Pudlák [Pud94] on which it relies, when that tool is
straightforwardly extended to super-constant depth.444The $\Omega(\cdot)$
notation in the circuit size lower bound of Gál _et al._ , for example,
Theorem 1 in [Gal+13], involves an implicit constant which decays with the
depth $d$, as can be suitable for constant depths; similarly for the tool of
Pudlák, Theorem 3.(ii) in [Pud94], on which it relies. For general super-
constant depths, more explicit work is required to verify the decay is not too
rapid.

######  Theorem 1.2.

(Lower bound) [Gal+13] Let $\rho\in(0,1)$ and $\delta\in(0,\frac{1}{2})$, and
let constant $c>0$. Let $C_{n}:\\{0,1\\}^{n}\to\\{0,1\\}^{\lfloor
n/\rho\rfloor}$ be a family of circuits of size at most $cn$ that encode
error-correcting codes with relative distance $\geq\delta$. Arbitrary Boolean-
function gates of unrestricted fanin are allowed in $C_{n}$. If $n$ is
sufficiently large, i.e., $n\geq N(r,\delta,c)$, the depth of the circuit
$C_{n}$ is at least $\alpha(n)-2$.

The proof for Theorem 1.2 closely follows [Gal+13] and is an application of a
graph-theoretic argument in the spirit of [Val77, Dol+83, Pud94, RS03]. In
detail, we use Pudlák’s size lower bounds [Pud94] on “densely regular” graphs,
and rely on the connection between good codes and densely regular graphs by
Gál _et al._ [Gal+13]. Pudlák’s bound was originally proved for bounded depth;
to apply it to unbounded depth, we explicitly determine the hidden constants
by directly following Pudlák’s work, and verify that their decay at higher
unbounded depths is moderate enough to allow the lower-bound method to give
superlinear bounds up to depth $\alpha(n)-3$. Even after our work, the precise
asymptotic complexity of encoding good codes remains an open question for $d$
in the range [$\omega(1)$, $\alpha(n)$ \- 3].

Stepping back to a higher-level view, the strategy of the graph-theoretic
lower-bound arguments in the cited and related works is as follows:

  * •

Prove any circuit computing the target function must satisfy some
superconcentrator-like connection properties;

  * •

Prove any graph satisfying the above connection properties must have many
edges;

  * •

Therefore, the circuit must have many wires.

Valiant [Val75, Val76, Val77] first articulated this kind of argument, and
proposed the definition of superconcentrators. Somewhat surprisingly, Valiant
showed that linear-size superconcentrators exist. As a result, one cannot
prove superlinear size bounds using this argument (when the depth is
unbounded). Dolev, Dwork, Pippenger, and Wigderson [Dol+83] proved
$\Omega(\lambda_{d}(n)\cdot n)$ lower bounds for bounded-depth (weak)
superconcentrators, which implies circuit lower bounds for functions
satisfying weak-superconcentrator properties. Pudlák [Pud94] generalized Dolev
_et al._ ’s lower bounds by proposing the definition of _densely regular
graphs_ , and proved lower bounds for bounded-depth densely regular graphs,
which implies circuit lower bounds for functions satisfying densely regular
property, including shifters, parity shifters, and Vandermonde matrices. Raz
and Shpilka [RS03] strengthened the aforementioned superconcentrator lower
bounds by proving a powerful graph-theoretic lemma, and applied it to prove
superlinear lower bounds for matrix multiplication. (This powerful lemma can
reprove all the above lower bounds.) Gál _et al._ [Gal+13] proved that any
circuits encoding good error-correcting codes must be densely regular. They
combined this with Pudlák’s lower bound on densely regular graphs [Pud94] to
obtain $\Omega(\lambda_{d}(n)\cdot n)$ size bounds for depth-$d$ circuits
encoding good codes.

All the circuit lower bounds mentioned above apply even to the powerful model
of _arbitrary-gate_ circuits, that is,

  * •

each gate has unbounded fanin,

  * •

a gate with fanin $s$ can compute any function from $\\{0,1\\}^{s}$ to
$\\{0,1\\}$,

  * •

circuit size is measured as the number of wires.

In this “arbitrary-gates” model, any function from $\\{0,1\\}^{n}$ to
$\\{0,1\\}^{m}$ can be computed by a circuit of size $mn$.

It is known that any circuits encoding good codes must satisfy some
superconcentrator-like connection properties [Spi96], [Gal+13]. Our other
result is a theorem in the _reverse_ direction in the algebraic setting over
large finite fields. Motivated by this connection, we study
_superconcentrator-induced codes_ (Definition 5.1), a subclass of maximum
distance separable (MDS) codes [LX04, GRS12], and observe its tight connection
with superconcentrators.

######  Theorem 1.3.

(Informal) Given any $(n,m)$-superconcentrator, one can convert it to a linear
arithmetic circuit encoding a code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ such
that

$\operatorname{dist}(C(x),C(y))\,\geq\,m-\operatorname{dist}(x,y)+1\quad\forall
x\not=y\in\mathbb{F}^{n}$ (1)

by replacing each vertex with an addition gate and assigning the coefficient
for each edge uniformly at random over a sufficiently large finite field
(where $d2^{\Omega(n+m)}$ suffices, and $d$ is the depth of the
superconcentrator).

We also observe that any arithmetic circuit, linear or nonlinear, encoding a
code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ satisfying (1), viewed as a graph,
must be a superconcentrator.

The proof of Theorem 1.3 relates the connectivity properties with the rank of
a matrix, and uses the Schwartz-Zippel lemma to estimate the rank of certain
submatrices; these techniques are widely used, for example, in [CKL13, Lov18].
In addition, the idea of assigning uniform random coefficients (in a finite
field) to edges, to form linear circuits, has appeared before in e.g. network
coding [Ahl+00, LYC03]. The question we study is akin to a higher-depth
version of the GM-MDS type questions about matrices with restricted support
[Lov18].

Observe that any code satisfying the distance inequality (1) is a good code.
The existence of depth-$d$ size-$O(\lambda_{d}(n)\cdot n)$ superconcentrators
[Dol+83, AP94], for any $d\geq 3$, immediately implies the existence of
depth-$d$ (linear) arithmetic circuits of size $O(\lambda_{d}(n)\cdot n)$
encoding good codes _over large finite field_.

In a subsequent work [Li23], inspired by this connection and using similar
techniques, the second author proved that any $(n,m)$-superconcentrator can
compute the shares of an $(n,m)$ linear threshold secret sharing scheme. In
other words, any $(n,m)$-superconcentrator-induced code induces an $(n,m)$
linear threshold secret sharing scheme. Results in [Li23] can be viewed as an
application of superconcentrator-induced codes.

###  1.2 Circuit construction techniques

In terms of techniques, Gál _et al._ proposed the notion of _range detectors_
(Definition 3.6). They use probabilistic methods to prove certain linear-size
depth-1 range detectors _exist_ and then compose the range detectors
_recursively_ to construct circuits encoding good codes. We improve the
recursive construction by tuning the parameters and changing the way range
detectors are composed (in the inductive step), which leads to an _absolute
constant_ in the size bound $O(\lambda_{d}(n)\cdot n)$, eliminating the
dependency on $d$. By utilizing a property of the inverse Ackermann function,
we immediately obtain circuits of depth $\alpha(n)$ and size $O(n)$, avoiding
a size-reduction argument.

Let us give an overview of the construction, highlighting the difference
between Gál _et al._ ’s. First, we distill some notions to facilitate the
construction, each of which is either explicit or present in essence in
[Gal+13].

  * •

Partial good code (i.e., Definition 3.1), or PGC for short: when the weight of
an input is within a certain range, a PGC outputs a codeword whose relative
weight is above an absolute constant.

  * •

Condenser: a condenser function reduces the number of inputs while preserving
the _minimum_ absolute weight. Using probabilistic arguments, Gál _et al._
proved that certain _unbalanced unique-neighbor expanders_ exist, and
converted the expanders to linear-size condensers, that is,
$\left(n,\lfloor\frac{n}{r}\rfloor,s,\frac{n}{r^{1.5}},s\right)$-range
detectors. We reuse their condensers.

  * •

Amplifier: these amplify the number of inputs while preserving the _relative
distance_. Gál _et al._ uses a probabilistic argument and applies the Chernoff
bound to show linear-size amplifiers exist (e.g., in the proof of Theorem 22
and Lemma 26). We choose to decouple the argument by using the disperser
graphs given by [RT00], choosing the coefficients at random, and then applying
a union bound.

  * •

Rate booster: these do not change the number of inputs, but can boost the rate
close to the Gilbert-Varshamov bound. Lemma 17 in [Gal+13] embodies a rate
booster, although a not fully optimized one; Gál _et al._ also state555In the
conference version (COCOON 2023), we mistakenly stated that such rate-boosting
is not discussed by Gál _et al._ (based on non-journal versions of the paper),
but in fact it is discussed in Section 4 of the journal version. that a
tighter analysis would approach the Gilbert-Varshamov bound. Using a
probabilistic argument similar to that with the amplifiers and to the argument
in [Gal+13], we provide a verification of this claim.

  * •

Composition Lemma: this tool allows us to combine $h$ partial good codes into
a larger one, at the cost of increasing the depth by 1, and the size by
$O(n)$. Furthermore, if each partial good code has bounded output fanin
$O(1)$, then one can _collapse_ the last layer at the cost of increasing the
size by $O(hn)$. The composition idea was implicit in Gál _et al._ ’s (e.g.,
in Theorem 22 and Lemma 26 in [Gal+13]).

With the these concepts, the task is to construct the circuits using these
building blocks. Our analysis framework is also inspired by [Dol+83]; we show
the minimal size of a depth-$d$ $(n,r,s)$-PGC satisfies a similar recursion as
that of _partial superconcentrators_. For the base case when the depth is
small (i.e., $d\leq 4$), we completely reuse Gál _et al._ ’s construction. In
the key inductive step, Gál _et al._ construct a depth-$(d+2)$ circuits
encoding an $\left(n,\frac{n}{r},n\right)$-PGC by composing a number of, say
$h$, PGCs. _Assuming_ each smaller PGC is of size $O(n)$, the total size would
be $O(hn)$. They let

$\begin{cases}k_{1}&=\,\min\\{r,\lceil m^{3/4}\rceil\\}\\\
k_{i+1}&=\,\lambda_{d}(k_{i})^{3},\end{cases}$ (2)

where $h$ is the least integer such that $k_{h}$ is below a particular
universal constant. Each inner part is an
$\left(\left\lfloor\frac{n}{\lambda_{d}(k_{i})^{2}}\right\rfloor,\frac{n}{k_{i}},\frac{n}{\lambda_{d}(k_{i})^{2}}\right)$-PGC
of depth $d$ and size $O_{d}(n)$, topped by a condenser, appended by an
ampilifier. Then they argue that $h=2\lambda_{d+2}(n)+O_{d}(1)$, and thus the
total size of the depth-$(d+2)$ circuit becomes $O_{d+2}(\lambda_{d+2}(n)\cdot
n)$. They did not mention the constant in $O_{d}(1)$; if one works out the
constant straightforwardly, it is a very fast-growing constant depending on
$d$.

Our remedy is to choose the parameters and compose the PGCs differently in the
inductive construction. To obtain a depth-$(d+2)$ circuit encoding an
$\left(n,\frac{n}{r},n\right)$-PGC, we compose at most $\lambda_{d+2}(n)$ PGCs
that are of the parameter
$\left(n,\frac{n}{A^{(i)}_{k-1}(c_{0})},\frac{n}{A^{(i-1)}_{k-1}(c_{0})}\right)$,
and of size $O(n)$, where $1\leq i\leq\lambda_{d+2}(n)$. In addition, we
ensure that each PGC has bounded output fanin $O(1)$, which allows us to
collapse the last layer in the composition lemma without blowing up the size.
Let $r=A^{(i-1)}_{k-1}(c_{0})$. To construct a depth-$(d+2)$
$\left(n,\frac{n}{A_{k-1}(r)},\frac{n}{r}\right)$-PGC, we cannot reduce it to
a depth-$d$ PGC directly, due to the parameter restriction in the condenser.
(Recall that the linear-size condenser constructed is an
$\left(n,\lfloor\frac{n}{r}\rfloor,s,\frac{n}{r^{1.5}},s\right)$-range
detector, not an
$\left(n,\lfloor\frac{n}{r}\rfloor,s,\frac{n}{r},s\right)$-range detector.) We
work around this by composing two PGCs: an
$\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)$-PGC, and an
$\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)$-PGC, where each is of linear
size, and have bounded output fanin $O(1)$. The former can be constructed by a
linear-size condenser, an
$\left(\left\lfloor\frac{n}{2r}\right\rfloor,\frac{n}{A(k-1,r)},\frac{n}{2r}\right)$-PGC
of depth $d$, and an amplifier; the latter we construct directly by a simple
argument. This composition is inspired by the superconcentrator construction
by Dolev _et al._ [Dol+83], who constructed superconcentrators of depth $d$
and size $O(\lambda_{d}(n)\cdot n)$. Indeed, the encoding circuits _have to_
resemble the superconcentrators, since it was known that the circuits must be
a (weak) superconcentrators.

The above sketch leads to a construction of depth-$d$
size-$O(\lambda_{d}(n)\cdot n)$ circuits encoding good codes, where $d$ is not
necessarily a constant; by letting $d=\alpha(n)$, one immediately gets
depth-$\alpha(n)$ size-$O(n)$ circuits. This improves the analysis, getting
rid of an additive $O(\log\alpha(n))$ factor in the depth (compared with
Corollary 32 in [Gal+13], or Corollary 1.1 in [Dol+83]). But a tight analysis
to prove this requires one small new ingredient compared to prior works.
Specifically, we observe that, if $\lambda_{d}(n)\leq d$, then
$\lambda_{d+2}(n)=O(1)$ (See Proposition A.2 (ii) for details.) The above
observation can also improve the depth bound on the linear-size
superconcentrators in [Dol+83] from $\alpha(n)+O(\log\alpha(n))$ to
$\alpha(n)$ (without change in the construction). In contrast, Gál _et al._
deployed a different strategy to achieve linear size. Having constructed an
encoding circuit of depth $d=O(1)$ and size $O_{d}(\lambda_{d}(n)\cdot n)$,
they then apply a size-reduction transformation $O(\log\lambda_{d}(n))$ times,
a transformation which reduces a size-$m$ instance to a size $m/2$ instance
with additional cost $O(m)$ wires. In this way they obtain a circuit of depth
$2d+O(\log\lambda_{d}(n))$ and size $O_{d}(n)$.

We verify our codes can obtain any constant rate and constant relative
distance within the Gilbert-Varshamov bound, by using a disperser graph at the
bottom layer and collapsing that layer afterward (for linear circuits). A
similar rate-boosting by probabilistic construction is described in [Gal+13];
see their (quantitatively somewhat weaker) Lemma 17 and Corollary 18 and the
comments following, stating an improved analysis is possible.

##  2 Inverse Ackermann functions

######  Definition 2.1.

(Definition 2.3 in [RS03]) For a function $f$, define $f^{(i)}$ to be the
composition of $f$ with itself $i$ times. For a function
$f:\mathbb{N}\to\mathbb{N}$ such that $f(n)<n$ for all $n>0$, define

$f^{*}(n)\,=\,\min\\{i:f^{(i)}(n)\leq 1\\}.$

Let

$\displaystyle\lambda_{1}(n)$ $\displaystyle\,=\,$
$\displaystyle\lfloor\sqrt{n}\rfloor\ ,$ $\displaystyle\lambda_{2}(n)$
$\displaystyle\,=\,$ $\displaystyle\lceil\log n\rceil\ ,$
$\displaystyle\lambda_{d}(n)$ $\displaystyle\,=\,$
$\displaystyle\lambda^{*}_{d-2}(n)\ .$

As $d$ gets larger, $\lambda_{d}(n)$ becomes extremely slowly growing, for
example, $\lambda_{3}(n)=\Theta(\log\log n)$,
$\lambda_{4}(n)=\Theta(\log^{*}n)$, $\lambda_{5}(n)=\Theta(\log^{*}n)$, etc.

We define a version of the inverse Ackermann function as follows.

######  Definition 2.2 (Inverse Ackermann Function).

For any positive integer $n$, let

$\alpha(n)\,=\,\min\\{\text{even }d:\lambda_{d}(n)\leq 6\\}.$

There are different variants of the inverse Ackermann function; they differ by
at most a multiplicative constant factor.

We need the definition of the Ackermann function. We put some relevant
properties in Appendix A.

######  Definition 2.3.

(Ackermann function [Tar75, Dol+83]) Define

$\begin{cases}A(0,j)\,=\,2j,&\text{for $j\geq 1$}\\\ A(i,1)\,=\,2,&\text{for
$i\geq 1$}\\\ A(i,j)\,=\,A(i-1,A(i,j-1)),&\text{for $i\geq 1,j\geq
2$}.\end{cases}$ (3)

The Ackermann function grows rapidly. From the definition, one can easily
verify that $A(0,i)=2i$, $A(1,i)=2^{i}$ and
$A(2,i)=\begin{matrix}\underbrace{2^{2^{{}^{.\,^{.\,^{.\,^{2}}}}}}}&\\\
i\mbox{ copies of }2&\end{matrix}.$ For notational convenience, we often write
$A(i,j)$ as $A_{i}(j)$.

##  3 Upper bound

In this section, we prove Theorem 1.1. That is, we non-explicitly construct,
for any rate $r\in(0,1)$ and relative distance $\delta\in(0,\frac{1}{2})$
satisfying $r<1-h(\delta)$, circuits encoding error-correcting codes
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{\lfloor n/r\rfloor}$ with relative distance
$\delta$, where the circuit is of size $O_{r,\delta}(\lambda_{d}(n)\cdot n)$
and depth $d$. In particular, when the depth $d=\alpha(n)$, the circuit is of
size $O_{r,\delta}(n)$.

First, we construct circuits encoding codes
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with relative distance $\frac{1}{8}$,
where the constants $32$ and $\frac{1}{8}$ are picked for convenience. Then,
we verify that one can boost the rate and the distance to achieve the Gilbert-
Varshamov bound (without increasing the depth of the circuit).

Note that random linear codes achieve the Gilbert-Varshamov bound. However,
circuits encoding random linear codes have size $O(n^{2})$. In contrast, our
circuits have size $O(n)$. Our circuits consist of XOR gates only; we call
these _linear circuits_ hereafter. We point out that the construction
generalizes to any finite field, where XOR gates are replaced by addition
gates (over that finite field).

Recall that let $S_{d}(n)$ denote the minimum size of a depth-$d$ linear
circuit encoding a code $C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with distance
$4n$.

######  Definition 3.1.

(Partial good code) $C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ is called _$(n,r,s)$
-partial good code_, or _$(n,r,s)$ -PGC_ for short, if for all
$x\in\\{0,1\\}^{n}$ with $\operatorname{wt}(x)\in[r,s]$, we have
$\operatorname{wt}(C(x))\geq 4n$.

Denote by $S_{d}(n,r,s)$ the minimum size of a linear circuit of depth-$d$
that encodes an $(n,r,s)$-PGC, where $r,s$ are real numbers.

######  Definition 3.2.

[Sip88, CW89] Bipartite graph $G=(V_{1}=[n],V_{2}=[m],E)$ is a _$(k,\epsilon)$
-disperser graph_ if for any $X\subseteq V_{1}$ with $|X|\geq k$,
$|\Gamma(X)|\geq(1-\epsilon)m$.

We rely on the following probabilistic construction of dispersers.

######  Theorem 3.3.

(Theorem 1.10 in [RT00]) For every $n\geq k>1$, $m\geq 1$, and $\epsilon>0$,
there exists a $(k,\epsilon)$-disperser graph $G=(V_{1}=[n],V_{2}=[m],E)$ with
left degree

$D\>=\>\left\lceil\frac{1}{\epsilon}\left(\ln\left(\frac{n}{k}\right)+1\right)+\frac{m}{k}\left(\ln\left(\frac{1}{\epsilon}\right)+1\right)\right\rceil.$

A _probabilistic (linear) circuit_ is a linear circuit with random
coefficients. That is, each XOR gate computes
$c_{1}x_{1}+c_{2}x_{2}+\ldots+c_{m}x_{m}$, where $x_{1},x_{2},\ldots,x_{m}$
are incoming wires, coefficients $c_{1},c_{2},\ldots,c_{n}\in\\{0,1\\}$ are
chosen independently and uniformly at random. A probabilistic circuit can be
viewed as a distribution of linear circuits. Our work in what follows relies
on the following simple observation: if one of the incoming wires is nonzero,
the output is uniformly distributed in $\\{0,1\\}$.

Figure 1: Gate in a probabilistic circuit

######  Lemma 3.4.

(Rate booster) Let $\delta\in(0,32)$, and let $c>1$,
$\gamma\in(0,\frac{1}{2})$ be such that $h(\gamma)<1-\frac{1}{c}$. For
sufficiently large $n\geq N(c,\gamma)$, there exists a probabilistic circuit
$C:\\{0,1\\}^{32n}\to\\{0,1\\}^{\lfloor cn\rfloor}$ of depth 1 and size
$O_{\delta,c,\gamma}(n)$ such that

$\Pr_{C}\left[\operatorname{wt}(C(x))\geq\gamma\cdot\lfloor
cn\rfloor\right]\>>\>1-2^{-n}$

for any $x\in\\{0,1\\}^{32n}$ with $\operatorname{wt}(x)\geq\delta n$.
Moreover, the output gates have bounded fanin $O_{\delta,c,\gamma}(1)$.

###### Proof.

Let $c^{\prime}=\frac{\lfloor cn\rfloor}{n}$. Let $n$ be sufficiently large
such that $h(\gamma)<1-\frac{1}{c^{\prime}}$.

By Theorem 3.3, there exists a $(\delta n,\epsilon)$-disperser graph
$G^{\prime}=(V_{1}=[32n],V^{\prime}_{2}=[(c^{\prime}+1)n],E)$, where
$\epsilon>0$ is small constant to be determined. After removing $n$ vertices
in $V^{\prime}_{2}=[(c^{\prime}+1)n]$ with the largest degree, we are left
with a bipartite graph $G=(V_{1}=[32n],V_{2}=[c^{\prime}n],E)$ such that

$|\Gamma(X)|\>\geq\>c^{\prime}n-\epsilon(c^{\prime}+1)n\>=\>c^{\prime}n\left(1-\epsilon-\frac{\epsilon}{c^{\prime}}\right)$
(4)

for all $X\subseteq V_{1}$ of size at least $\delta n$. Moreover, the degree
of the vertices in $V_{2}$ is bounded by $32D$, where
$D=\left\lceil\frac{1}{\epsilon}(\ln(\frac{32}{\delta})+1)+\frac{c^{\prime}+1}{\delta}(\ln(\frac{1}{\epsilon})+1)\right\rceil=O_{\delta,c,\epsilon}(1).$

We transform bipartite graph $G$ into a probabilistic circuit by identifying
vertices in $V_{1}$ with $32n$ inputs, denoted by
$x_{1},x_{2},\ldots,x_{32n}$, and replacing each vertex in $V_{2}$ by an XOR
gate with random coefficients. That is, if vertex $j\in V_{2}$ is connected to
$i_{1},i_{2},\ldots,i_{k}\in V_{1}$, then vertex $j$ computes an output

$y_{j}\>=\>c_{j,i_{1}}x_{i_{1}}+c_{j,i_{2}}x_{i_{2}}+\ldots+c_{j,i_{k}}x_{i_{k}}\pmod{2},$

where $c_{j,i_{1}},c_{j,i_{2}},\ldots,c_{j,i_{k}}\in\\{0,1\\}$ are chosen
independently and uniformly at random.

For any $x\in\\{0,1\\}^{32n}$ with $\operatorname{wt}(x)\geq\delta n$, let
$X=\operatorname{supp}(x)$. By the expansion property (4), we have
$|\Gamma(X)|\geq c^{\prime}n(1-\epsilon^{\prime})$, where
$\epsilon^{\prime}=(1+\frac{1}{c^{\prime}})\epsilon$. For every
$j\in\Gamma(X)$, vertex $j$ is incident to at least one vertex in $X$; pick an
arbitrary neighbor, denoted by $i\in X$, and leave coefficient $c_{i,j}$
unfixed. In other words, we fix all the coefficients except those
$|\Gamma(X)|$ coefficients (that are incident to $X$). Observe that $C(x)$,
restricted to $\Gamma(X)$, is uniformly distributed in
$\\{0,1\\}^{|\Gamma(X)|}$. Thus,

$\displaystyle\Pr_{C}[\operatorname{wt}(C(x))<\gamma c^{\prime}n]$
$\displaystyle\leq$ $\displaystyle\frac{{\lceil
c^{\prime}n(1-\epsilon^{\prime})\rceil\choose 0}+{\lceil
c^{\prime}n(1-\epsilon^{\prime})\rceil\choose 1}+\ldots+{\lceil
c^{\prime}n(1-\epsilon^{\prime})\rceil\choose\lfloor\gamma
c^{\prime}n\rfloor}}{2^{\lceil c^{\prime}n(1-\epsilon^{\prime})\rceil}}$ (5)
$\displaystyle\leq$ $\displaystyle
2^{-c^{\prime}n(1-\epsilon^{\prime})(1-h(\frac{\gamma}{1-\epsilon^{\prime}}))}.$

Recall that $\epsilon^{\prime}=(1+\frac{1}{c^{\prime}})\epsilon$. Let
$\epsilon>0$ be sufficiently small such that
$c^{\prime}(1-\epsilon^{\prime})(1-h(\frac{\gamma}{1-\epsilon^{\prime}}))>1$,
the probability (5) would be less than $2^{-n}$. (Such $\epsilon^{\prime}>0$
clearly exists, since $h(\gamma)<1-\frac{1}{c^{\prime}}\Leftrightarrow
c^{\prime}(1-h(\gamma))>1$). ∎

Next, a “composition lemma” allows us to combine several partial good codes
into a larger one. The lemma is already implicit in [Gal+13].

######  Lemma 3.5.

(Composition Lemma) For any $n,d\geq 1$, $\ell\geq 2$, and any $1\leq
r_{1}\leq r_{2}\leq\ldots r_{\ell+1}\leq n$, assume there exist linear
circuits of size $s_{i}$ and depth $d$ encoding some $(n,r_{i},r_{i+1})$-PGC,
$i=1,2,\ldots,\ell$. We have

$S_{d+1}(n,r_{1},r_{\ell+1})\,\,\leq\,\,\sum_{i=1}^{\ell}s_{i}+O(n).$ (6)

Moreover, if the output gates of the linear circuits encoding
$(n,r_{i},r_{i+1})$-PGCs have bounded fan-in $D$, for all $i=1,2,\ldots,\ell$,
then we have

$S_{d}(n,r_{1},r_{\ell+1})\,\,\leq\,\,\sum_{i=1}^{\ell}s_{i}+O(D\ell n).$ (7)

In addition, the fanin of the output gates (of the depth-$d$ circuit encoding
the $(n,r_{1},r_{\ell+1})$-PGC) is bounded by $O(\ell D)$.

###### Proof.

Denote the linear circuit encoding an $(n,r_{i},r_{i+1})$-PGC by $C_{i}$,
$i=1,2,\ldots,\ell$. Recall that each $C_{i}:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$
has $32n$ outputs, denoted by $w_{1}^{(i)},w_{2}^{(i)},\ldots,w_{32n}^{(i)}$.

Create $32n$ gates, denoted by $y_{1},y_{2},\ldots,y_{32n}$. Let

$y_{j}\,\,=\,\,\sum_{i=1}^{\ell}c_{j}^{(i)}w_{j}^{(i)}\pmod{2},$

where coefficients $c_{j}^{(i)}\in\\{0,1\\}$ are chosen independently and
uniformly at random. See Figure 2 for illustration.

Figure 2: Partial good codes composition

Figure 2 is a bit misleading. Instead of creating $32n$ new gates
$y_{1},y_{2},\ldots,y_{32n}$, we _merge_
$w_{j}^{(1)},w_{j}^{(2)},\ldots,w_{j}^{(\ell)}$, for each $j=1,2,\ldots,32n$.
Fixing $j$, independently for each $i\in\\{1,2,\ldots,\ell\\}$, with
probability $\frac{1}{2}$, merge $w_{j}^{(i)}$ with $y_{j}$, and with
probability $\frac{1}{2}$, do nothing. As such, the depth of the circuit is
still $d$, and the size is at most $\sum_{i=1}^{\ell}s_{i}$.

Let us analyze the weight of
$y=(y_{1},y_{2},\ldots,y_{32n})\in\\{0,1\\}^{32n}$. For any
$x\in\\{0,1\\}^{n}$ with $\operatorname{wt}(x)\in[r_{1},r_{\ell+1}]$, there
exists $k$ such that $\operatorname{wt}(x)\in[r_{k},r_{k+1}]$. By the
definition of PGC, $C_{k}(x)$ has weight at least $4n$. Fix all coefficients
$c_{j}^{(i)}$ except for those $i=k$ and $j\in\operatorname{supp}(C_{k}(x))$,
one can easily see that $\\{y_{j}:j\in\operatorname{supp}(C_{k}(x))\\}$ is
uniformly distributed in $\\{0,1\\}^{|\operatorname{supp}(C_{k}(x))|}$. Thus,
for any fixed $x$,

$\displaystyle\Pr\left[\operatorname{wt}(y)<\frac{n}{2}\right]$
$\displaystyle\,\leq\,$ $\displaystyle\frac{{4n\choose 0}+{4n\choose
1}+\ldots+{4n\choose\lfloor\frac{n}{2}\rfloor}}{2^{4n}}$
$\displaystyle\,\leq\,$ $\displaystyle
2^{-4n(1-h(\frac{1}{8}))}\,\,<\,\,2^{-1.8n}.$

Taking a union bound over $x$, we know there exists an assignment of
coefficients such that the weight of the output is always $\geq\frac{n}{2}$.

Finally, we boost the distance from $\frac{1}{2}n$ to $4n$ using a rate
booster in Lemma 3.4. Specifically, apply Lemma 3.4 with
$\delta=\frac{1}{2},c=32,\gamma=\frac{1}{8}$. Adding the rate booster
increases the depth by 1, and increases the size by $O(n)$.

For the “moreover” part, observe that the outputs in the rate booster have
bounded fan-in $O(1)$. As in the use of rate boosting in [Gal+13], we collapse
the last layer, where, originally, the last layer has bounded fan-in $O(1)$,
and the second last layer has fan-in $\leq\ell D$. As such, $O(n)$ wires in
the rate booster will extend to $O(D\ell n)$ wires, which proves (7).
Furthermore, the output gates have fanin $O(\ell D)$. ∎

######  Definition 3.6.

[Gal+13] An _$(m,n,\ell,k,r,s)$ -range detector_ is a linear circuit that has
$m$ inputs, $n$ outputs, and on any input of Hamming weight between $\ell$ and
$k$, it outputs a string with Hamming weight between $r$ and $s$. We omit the
last parameter if $s=n$.

######  Lemma 3.7.

(Condenser, Lemma 23 in [Gal+13]) There exists a constant $c_{0}\geq 6$ such
that for any $c_{0}\leq r\leq n$ and $1\leq s\leq\frac{n}{r^{1.5}}$, where $n$
is an integer, $r,s$ are reals, there exists an
$\left(n,\lfloor\frac{n}{r}\rfloor,s,\frac{n}{r^{1.5}},s\right)\text{-range
detector}$ of depth 1 and size $6n$.

The following lemma says there exist linear size “amplifiers” that amplify the
number of outputs while preserving the relative distance.

######  Lemma 3.8 (Amplifier).

For any positive integers $n,m\geq 3n$, there exists an
$(n,m,\frac{n}{8},n,\frac{m}{8})$-range detector computable by a depth-1
linear circuit of size $O(m)$. Moreover, the fanin of the outputs is bounded
by an absolute constant.

###### Proof.

By Theorem 3.3, there exists a bipartite graph $G=(V_{1}=[n],V_{2}=[m],E)$
with $O(m)$ edges such that for every $X\subseteq V_{1}$ of size at least
$\frac{n}{8}$, $|\Gamma(X)|\geq\frac{9}{10}\cdot m$. In addition, the vertices
in $V_{2}$ have bounded degrees. (For example, applying Theorem 3.3 with
$n=m$, $m=2m$, $k=\frac{n}{8}$, and $\epsilon=\frac{1}{20}$, we have a
disperser with left degree $O(\frac{m}{n})$ and right average degree $O(1)$.
After removing $m$ right vertices with largest degree, we have the desired
graph.)

Convert graph $G$ into a probabilistic circuit
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$ as follows:

  * •

View the vertices in $V_{1}$ as inputs, denoted by $x_{u}$, for each $u\in
V_{1}$.

  * •

Replace the vertices in $V_{2}$ by XOR gates. View them as outputs, denoted by
$y_{v}$, for each $v\in V_{2}$.

  * •

For each edge $(u,v)\in E$, choose a coefficient $c_{u,v}\in\\{0,1\\}$
independently at random. Let the output gate $v$ compute the function

$y_{v}\>=\>\sum_{(u,v)\in E}c_{u,v}x_{u}\pmod{2}.$

For any $x\in\\{0,1\\}^{n}$ with $\operatorname{wt}(x)\geq\frac{n}{8}$, by the
expansion property of graph $G$,
$|\Gamma(\operatorname{supp}(x))|\geq\frac{9}{10}\cdot m$. In other words,
there exist at least $\lceil\frac{9}{10}\cdot m\rceil$ outputs, which are
incident to at least one nonzero input. So, $C(x)$, restricted to
$\Gamma(\operatorname{supp}(x))$, is uniformly distributed in
$\\{0,1\\}^{|\Gamma(\operatorname{supp}(x))|}$. Thus,

$\displaystyle\Pr[\operatorname{wt}(C(x))<\frac{m}{8}]$
$\displaystyle\,\,\leq\,\,$ $\displaystyle\frac{{\lceil\frac{9}{10}\cdot
m\rceil\choose 0}+{\lceil\frac{9}{10}\cdot m\rceil\choose
1}+\ldots+{\lceil\frac{9}{10}\cdot
m\rceil\choose\lfloor\frac{m}{8}\rfloor}}{2^{\lceil\frac{9}{10}\cdot
m\rceil}}$ $\displaystyle\,\,\leq\,\,$ $\displaystyle
2^{-(1-h(\frac{5}{36}))\cdot\frac{9}{10}m}$ $\displaystyle\,\,<\,\,$
$\displaystyle 2^{-0.37m}\,\,<\,\,2^{-n}.$

Finally, taking a union bound over all $x$, we conclude there exists a linear
circuit that computes an $(n,m,\frac{n}{8},n,\frac{m}{8})$-range detector. ∎

The following lemma says, by putting a condenser at the top and an amplifier
at the bottom, one can reduce the size of the problem (of encoding partial
good codes).

######  Lemma 3.9.

(Reduction Lemma) Let $c_{0}$ be the constant in Lemma 3.7. For any
$r\in[c_{0},n]$ and $1\leq s\leq t\leq\frac{n}{r^{1.5}}$,

$S_{d}(n,s,t)\,\,\leq\,\,S_{d-2}\left(\left\lfloor\frac{n}{r}\right\rfloor,s,\frac{n}{r}\right)+O(n).$
(8)

In addition, the output gates encoding $(n,s,t)$-PGC have bounded fanin
$O(1)$.

###### Proof.

Construct a depth-$d$ linear circuit that encodes an $(n,s,t)$-PGC by
concatenating three circuits:

  * •

(Condenser) The top is an $(n,\lfloor\frac{n}{r}\rfloor,s,t,s)$-range detector
of size $O(n)$ and depth 1, whose existence is proved by Lemma 3.7.

  * •

(Partial good code) The middle is an
$(\lfloor\frac{n}{r}\rfloor,s,\lfloor\frac{n}{r}\rfloor)$-PGC of depth $d-2$.

  * •

(Amplifier) The bottom is an
$(32\lfloor\frac{n}{r}\rfloor,32n,4\lfloor\frac{n}{r}\rfloor,32\lfloor\frac{n}{r}\rfloor,4n)$-range
detector of depth 1 and size $O(n)$, whose existence is proved by Lemma 3.8.
Moreover, the output gates have bounded fanin $O(1)$.

The output gates of the overall circuit have bounded fanin $O(1)$, because the
output gates of the amplifier have bounded fanin $O(1)$. ∎

The following bounds are tight for fixed depth $d$. To avoid redoing the same
work, we will use it for the case $d=4$ at the base step in our main
construction. Our technical contribution is to remove the dependence on $d$,
i.e., we prove $S_{d}=O(\lambda_{d}(n)\cdot n)$ for any $d$, not necessarily
fixed, where the hidden constant is an absolute constant.

######  Lemma 3.10.

(Lemma 28 in [Gal+13]) Fix an even constant $d\geq 4$. For any $1\leq r\leq
n$,

$S_{d}\left(n,\frac{n}{r},n\right)\,\,=\,\,O_{d}(\lambda_{d}(r)\cdot n),$

where the constant in $O_{d}(\lambda_{d}(r)\cdot n)$ only depends on $d$.

######  Lemma 3.11.

(Lemma 27 in [Gal+13]) For any $1\leq r\leq n$,

$S_{2}\left(n,\frac{n}{r},n\right)\,\,=\,\,O(n\log^{2}r).$

We will need the following handy result in our recursive construction.

######  Lemma 3.12.

For any $1\leq r\leq n$,

$S_{4}\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)\,\,=\,\,O(n)\ ,$

where the constant in $O(n)$ is an absolute constant. Moreover, the output
gates of the linear circuits have bounded fanin $O(1)$, which is an absolute
constant.

###### Proof.

We apply Lemma 3.9 with $r=\lfloor\sqrt{r}\rfloor$, $s=\frac{n}{4r^{2}}$,
$t=\frac{n}{r}$. Thus,

$\displaystyle S_{4}\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)$
$\displaystyle\leq$ $\displaystyle
S_{2}\left(\left\lfloor\frac{n}{\lfloor\sqrt{r}\rfloor}\right\rfloor,\frac{n}{4r^{2}},\frac{n}{\lfloor\sqrt{r}\rfloor}\right)+O(n)$
$\displaystyle\leq$ $\displaystyle
O\left(\frac{n}{\lfloor\sqrt{r}\rfloor}\log^{2}{(4r^{2})}\right)+O(n)\quad\quad\text{By
Lemma \ref{lem:ub_d2}}$ $\displaystyle=$ $\displaystyle O(n)\ .$

The output gates have bounded fanin $O(1)$ by Lemma 3.9. ∎

The following theorem is our main construction, which is proved by an
induction on the depth.

######  Theorem 3.13.

Let $c_{0}$ be the constant in Lemma 3.7. There exist absolute constants
$c,D>0$ such that the following holds.

For any $c_{0}\leq r\leq n$, and for any $k\geq 3$, we have

$S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)\;\leq\;2cn.$ (9)

Moreover, the output gates of the linear circuits encoding
$\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)$-PGC have bounded fanin $D$.

For any $2\leq r\leq n$ and for any $k\geq 2$,

$S_{2k}\left(n,\frac{n}{r},n\right)\;\leq\;3c\lambda_{2k}(r)\cdot n.$ (10)

(But the circuit encoding $\left(n,\frac{n}{r},n\right)$-PGC does not
necessarily have bounded output fanin.)

Figure 3: Inductive proof of Theorem 3.13

###### Proof.

(of Theorem 3.13) The overall proof is an induction on $k$, as illustrated by
Figure 3.

We pick constants $D,c$ such that

$D\,\geq\,2c_{2}\max(D_{1},D_{2})$

and

$c\,\geq\,\max\left(c_{1}D+(\log
c_{0})^{2}c_{3},2(2c_{1}D_{1}+c_{4}+c_{5}),c_{6}\right).$

Relevant constants used in the proof are summarized in Table 1 on page 1.

The base step is (10) for $k=2$, which is true by Lemma 3.10.

$c_{0}$ | the constant in Lemma 3.7 and 3.9
---|---
$c_{1}$ |  the constant in (7) in Lemma 3.5, i.e., $S_{d}(n,r_{1},r_{\ell+1})\,\,\leq\,\,\sum_{i=1}^{\ell}s_{i}+c_{2}D\ell n.$
$c_{2}$ |  Lemma 3.5, the fanin of the output gates (of the depth-$d$ circuit encoding the $(n,r_{1},r_{\ell+1})$-PGC) is bounded by $c_{2}\ell D$
$c_{3}$ | Lemma 3.11, $S_{2}\left(n,\frac{n}{r},n\right)\leq c_{3}n\log^{2}r$
$c_{4}$ |  the constant in (8) in Lemma 3.9, i.e., $S_{d}(n,s,t)\leq S_{d-2}\left(\left\lfloor\frac{n}{r}\right\rfloor,s,\frac{n}{r}\right)+c_{4}n$
$c_{5}$ |  the constant in Lemma 3.12, i.e., $S_{4}\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)\leq c_{5}n$
$c_{6}$ |  when $d=4$, the constant in $O_{d}(\lambda_{d}(r)\cdot n)$ in Lemma 3.10, i.e., $S_{4}\left(n,\frac{n}{r},n\right)\leq c_{6}\lambda_{4}(r)\cdot n$
$D_{1}$ | Lemma 3.9, output gates have fanin at most $D_{1}$
$D_{2}$ | Lemma 3.12, output gates have fanin at most $D_{2}$
Table 1: Absolute constants used in the proof.

For the induction step, we shall prove

  * •

(9) implies (10) for the same $k$, and

  * •

(10) with $k-1$ implies (9) with $k$.

First, let us prove (9) implies (10) for the same $k$, where $k\geq 3$. By the
composition lemma (i.e., Lemma 3.5),

$\displaystyle S_{2k}\left(n,\frac{n}{r},n\right)$ $\displaystyle\leq$
$\displaystyle
S_{2k}\left(n,\frac{n}{c_{0}},n\right)+\sum_{i=2}^{h}S_{2k}\left(n,\frac{n}{A^{(i)}_{k-1}(c_{0})},\frac{n}{A^{(i-1)}_{k-1}(c_{0})}\right)+c_{1}Dhn\
,$

where $h$ is the minimum integer such that $A^{(h)}_{k-1}(c_{0})\geq r$ (and
hence $A^{(h-1)}_{k-1}(c_{0})<r$). Note that $A^{(h)}_{k-1}(c_{0})\geq
A^{(h)}_{k-1}(1)=A(k,h)$ and $A^{(h-1)}_{k-1}(c_{0})\geq A(k,h-1)$. Since
$A(k,h-1)\leq A^{(h-1)}_{k-1}(c_{0})<r$, by Proposition A.3, we have
$h\leq\lambda_{2k}(r)$. By Lemma 3.11,
$S_{2k}\left(n,\frac{n}{c_{0}},n\right)\leq c_{3}n(\log c_{0})^{2}$, and the
circuit encoding $\left(n,\frac{n}{c_{0}},n\right)$-PGC has output fanin 1,
which can be done by adding an extra layer to the depth-2 circuit given by
Lemma 3.11. By induction hypothesis,
$S_{2k}\left(n,\frac{n}{A^{(i)}_{k-1}(c_{0})},\frac{n}{A^{(i-1)}_{k-1}(c_{0})}\right)\leq
2cn$, and the fanin of the outputs in the circut encoding
$\left(n,\frac{n}{A^{(i)}_{k-1}(c_{0})},\frac{n}{A^{(i-1)}_{k-1}(c_{0})}\right)$-PGC
is at most $D$. Thus

$\displaystyle S_{2k}\left(n,\frac{n}{r},n\right)$ $\displaystyle\leq$
$\displaystyle c_{3}n(\log c_{0})^{2}+(\lambda_{2k}(r)-1)\cdot
2cn+c_{1}D\lambda_{2k}(r)n$ $\displaystyle\leq$ $\displaystyle
2c\lambda_{2k}(r)n+\lambda_{2k}(r)n(c_{1}D+(\log c_{2})^{2}c_{3})$
$\displaystyle\leq$ $\displaystyle 3c\lambda_{2k}(r)\cdot n,$

since $c\geq c_{1}D+(\log c_{2})^{2}c_{3}$.

Now, we prove (10) with $k-1$ implies (9) with $k$. That is, assuming
$S_{2(k-1)}\left(n,\frac{n}{r},n\right)\leq 3c\lambda_{2(k-1)}(r)\cdot n$ for
any $2\leq r\leq n$, we will prove
$S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)\leq 2cn$ for any
$r\in[c_{0},n]$, and the output gates of the linear circuit encoding
$S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)$-PGC have bounded fanin
$\leq D$.

Note that $r\geq c_{0}$ by our condition. Applying the reduction lemma (i.e.,
Lemma 3.9) with $r^{\prime}=2r$, we have

$\displaystyle S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)$
$\displaystyle\leq$ $\displaystyle
S_{2(k-1)}\left(\left\lfloor\frac{n}{2r}\right\rfloor,\frac{n}{A(k-1,r)},\frac{n}{2r}\right)+c_{4}n$
$\displaystyle\leq$ $\displaystyle
3c\cdot\frac{n}{2r}\cdot\lambda_{2(k-1)}\left(\frac{A(k-1,r)}{2r}\right)+c_{4}n\quad\quad\text{By
induction hypothesis}$ $\displaystyle\leq$ $\displaystyle\frac{3c}{2}\cdot
n+c_{4}n,$

where the last step
$\lambda_{2(k-1)}\left(\frac{A(k-1,r)}{2r}\right)\leq\lambda_{2(k-1)}(A(k-1,r))=r$
is by Proposition A.3. By the reduction lemma (i.e., Lemma 3.9), the output
gates of the linear circuit encoding
$\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)$-PGC have bounded fanin
$D_{1}$.

Applying the composition lemma (i.e., Lemma 3.5), we have

$\displaystyle S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)$
$\displaystyle\leq$ $\displaystyle
S_{2k}\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)+S_{2k}\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)+2c_{1}D_{1}n$
$\displaystyle\leq$ $\displaystyle\frac{3c}{2}\cdot
n+c_{4}n+c_{5}n+2c_{1}D_{1}n$ $\displaystyle\leq$ $\displaystyle 2cn\ ,$

where the second last step is by Lemma 3.12, and the last step is because
$c\geq 2(2c_{1}D_{1}+c_{4}+c_{5})$. We claim the output gates of the overall
linear circuit encoding $\left(n,\frac{n}{A(k-1,r)},\frac{n}{r}\right)$-PGC
have fanin at most $2c_{2}\max(D_{1},D_{2})$, because

  * •

The output gates of the circuit encoding
$\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)$-PGC have bounded fanin
$D_{1}$ by the reduction lemma (i.e., Lemma 3.9). (Notice that the circuit
encoding
$\left(\left\lfloor\frac{n}{2r}\right\rfloor,\frac{n}{A(k-1,r)},\frac{n}{2r}\right)$-PGC
does not have bounded outputs fanin, which lies in the _inner part_ in the
reduction lemma.)

  * •

The output gates of the depth-$2k$ circuit encoding
$\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)$-PGC have bounded fanin $D_{2}$
by Lemma 3.12.

  * •

In the composition lemma (i.e., Lemma 3.5), we compose 2 circuits, encoding
$\left(n,\frac{n}{A(k-1,r)},\frac{n}{4r^{2}}\right)$-PGC and
$\left(n,\frac{n}{4r^{2}},\frac{n}{r}\right)$-PGC respectively. So the fanin
of the outputs of the overall circuit is bounded by $2c_{2}\max(D_{1},D_{2}),$
as desired.

∎

By taking $r=n$ in Theorem 3.13, we immediately have

######  Corollary 3.14.

For any $n$,

$S_{\alpha(n)}(n)\;=\;O(n).$

We have constructed a linear circuit of size $O(n)$ and depth $\alpha(n)$
encoding a code $C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with relative distance
$\frac{1}{8}$. By putting a rate booster at the bottom, one can achieve any
constant rate and relative distance within the Gilbert-Varshamov bound.

###### Proof.

(of Theorem 1.2) By Corollary 3.14, there exists a linear circuit of size
$O(\lambda_{d}(n)\cdot n)$ and depth $d$ encoding a code
$C:\\{0,1\\}^{n}\to\\{0,1\\}^{32n}$ with relative distance $\frac{1}{8}$.

By Lemma 3.4 with $c=\frac{1}{r}$, $\gamma=\delta$, $\delta=4$, we know there
exists a probabilistic circuit $D:\\{0,1\\}^{32n}\to\\{0,1\\}^{\lfloor
n/r\rfloor}$ of depth $1$ and size $O_{r,\delta}(n)$ such that

$\Pr_{D}\left[\operatorname{wt}(D(x))\geq\delta\cdot\left\lfloor\frac{n}{r}\right\rfloor\right]\;>\;1-2^{-n}$

for any $x\in\\{0,1\\}^{32n}$ with $\operatorname{wt}(x)\geq 4n$. Applying a
union bound over all $C(x)$, where $0\not=x\in\\{0,1\\}^{n}$, we claim there
exists a (deterministic) linear circuit $D$ of depth $1$ and size
$O_{r,\delta}(n)$ such that
$\operatorname{wt}(D(C(x)))\geq\delta\cdot\lfloor\frac{n}{r}\rfloor$ for all
nonzero $x\in\\{0,1\\}^{n}$. In addition, the output gates in circuit $D$ have
bounded fanin $O_{r,\delta}(1)$.

Note that the size of the circuit $D(C(x))$ is
$O(n)+O_{r,\delta}(n)=O_{r,\delta}(n)$ and the depth of the circuit is $d+1$.
Notice that the output gates have bounded fanin $O_{r,\delta}(1)$. So
collapsing the last layer (for the linear circuit) will increase the size by a
multiplicative factor $O_{r,\delta}(1)$. As such, we obtain a circuit of depth
$d$ and size $O_{r,\delta}(n)$.

In particular, by letting $d=\alpha(n)$, we obtain a circuit of depth
$\alpha(n)$ and size $O_{r,\delta}(n)$. ∎

##  4 Depth lower bound

######  Definition 4.1.

(Densely regular graph [Pud94]) Let $G$ be a directed acyclic graph with $n$
inputs and $n$ outputs. Let $0<\epsilon,\delta$ and $0\leq\mu\leq 1$. We say
$G$ is _$(\epsilon,\delta,\mu)$ -densely regular_ if for every $k\in[\mu
n,n]$, there are probability distributions $\mathcal{X}$ and $\mathcal{Y}$ on
$k$-element subsets of inputs and outputs respectively, such that for every
$i\in[n]$,

$\Pr_{X\in\mathcal{X}}[i\in X]\;\leq\;\frac{k}{\delta n}\
,\quad\quad\Pr_{Y\in\mathcal{Y}}[i\in Y]\;\leq\;\frac{k}{\delta n}\ ,$

and the expected number of vertex-disjoint paths from $X$ to $Y$ is at least
$\epsilon k$ for randomly chosen $X\in\mathcal{X}$ and $Y\in\mathcal{Y}$.

Denote by $D(n,d,\epsilon,\delta,\eta)$ the minimal size of a
$(\epsilon,\delta,\mu)$-densely regular layered directed acyclic graph with
$n$ inputs and $n$ outputs and depth $d$.

######  Theorem 4.2.

(Theorem 3 in [Pud94]) Let $\epsilon,\delta>0$. For every $d\geq 3$, and every
$r\leq n$,

$D\left(n,d,\epsilon,\delta,\frac{1}{r}\right)\;=\;\Omega_{d,\epsilon,\delta}\left(n\lambda_{d}(r)\right).$

To apply the above lower bounds when $d$ is not _fixed_ , we need to figure
out the hidden constant that depends on $d,\epsilon,\delta$.

######  Theorem 4.3.

Let $\epsilon,\delta>0$. For every $d\geq 3$, and every $r\leq n$,

$D\left(n,d,\epsilon,\delta,\frac{1}{r}\right)\;\geq\;\Omega\left(2^{-d/2}\epsilon\delta^{2}\lambda_{d}(r)n\right).$

The constant in $\Omega(2^{-d/2}\epsilon\delta^{2}\lambda_{d}(r)n)$ is an
absolute constant. The proof of Theorem 4.3 is almost the same as Theorem 4.2,
which is in Appendix B.

######  Corollary 4.4.

(Corollary 15 in [Gal+13]) Let $0<\rho,\delta<1$ be constants and $C$ be a
circuit encoding an error-correcting code $\\{0,1\\}^{\rho n}\to\\{0,1\\}^{n}$
with relative distance at least $\delta$. If we extend the underlying graph
with $(1-\rho)n$ dummy inputs, then its underlying graph is
$(\rho\delta,\rho,\frac{1}{n})$-densely regular.

The proof of Theorem 1.2 readily follows from Theorem 4.3 and Corollary 4.4.

###### Proof.

(of Theorem 1.2) By Corollary 4.4, the underlying graph $G$ of the circuit
$C_{n}$, is $\left(\rho^{\prime}\delta,\rho^{\prime},\frac{1}{\lfloor
n/\rho\rfloor}\right)$-densely regular with $\lfloor n/\rho\rfloor$ inputs and
$\lfloor n/\rho\rfloor$ outputs, by adding dummy inputs, where
$\rho^{\prime}=\frac{n}{\lfloor n/\rho\rfloor}>\frac{1}{2}\rho.$

Notice that graph $G$ is not necessarily layered. We can always make $G$
layered, by increasing the size by a factor of $d$, where $d$ is the depth of
$G$. By slightly abusing notations, we use $G$ to denote a layered
$(\rho^{\prime}\delta,\rho^{\prime},\frac{1}{\lfloor n/\rho\rfloor})$-densely
regular graph of depth $d$, where $|E(G)|\leq cdn$.

On the other hand, by Theorem 4.3, we have

$|E(G)|\;\geq\;\Omega\left(2^{-d/2}\delta\rho^{\prime 3}\lambda_{d}(\lfloor
n/\rho\rfloor)\lfloor n/\rho\rfloor\right).$

Combining with $|E(G)|\leq cdn$, we have

$\lambda_{d}(\lfloor n/\rho\rfloor)\leq O\left(\frac{1}{\delta\rho^{\prime
2}}cd2^{d/2}\right)=O_{\rho,\delta,c}\left(d2^{d/2}\right).$ (11)

Therefore,

$\displaystyle\lambda_{d+2}(n)\;\;\leq\;\;$
$\displaystyle\lambda_{d+2}(\lfloor n/\rho\rfloor)$ $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{d}^{*}(\lfloor n/\rho\rfloor)$
$\displaystyle\;\;\leq\;\;$ $\displaystyle\lambda_{d}^{*}(\lambda_{d}(\lfloor
n/\rho\rfloor))+1$ By Definition 2.1 $\displaystyle\;\;\leq\;\;$
$\displaystyle\lambda_{d}^{*}(O_{\rho,\delta,c}(1)\cdot d2^{d/2})+1$ By (11)
$\displaystyle\;\;\leq\;\;$
$\displaystyle\lambda_{d}^{*}(\lambda_{d}(O_{\rho,\delta,c}(1)\cdot
d2^{d/2}))+2$ By Definition 2.1 $\displaystyle\;\;\leq\;\;$
$\displaystyle\lambda_{d}^{*}(d)+2$ By Proposition A.4
$\displaystyle\;\;\leq\;\;$ $\displaystyle 6.$ By Proposition A.2

So, we conclude $d+2\geq\alpha(n)$, i.e., $d\geq\alpha(n)-2$. ∎

We would like to point out that, alternatively, one can use a powerful lemma
by Raz and Shipilka [RS03], to prove the depth lower bound (i.e., Theorem
1.2).

##  5 Superconcentrator-induced codes

It is already known that circuits for encoding error-correcting codes must
satisfy some superconcentrator-like connectivity properties. For example,
Speilman [Spi96] observed that any circuits encoding codes from
$\\{0,1\\}^{n}$ to $\\{0,1\\}^{m}$ with distance $\delta m$ must have $\delta
n$ vertex-disjoint paths connecting any chosen $\delta n$ inputs to any set of
$(1-\delta)m$ outputs; using matroid theory, Gál _et al._ [Gal+13] proved
that, for any $k\leq n$, for any $k$-element subset of inputs $X$, taking a
random $k$-element subset of outputs $Y$, the expected number of vertex-
disjoint paths from $X$ to $Y$ is at least $\delta k$.

We observe a connection in the _reverse_ direction by showing that _any_
superconcentrator graph, converted to an arithmetic circuit over a
sufficiently large field, can encode a good code. (Recall that a directed
acyclic graph $G=(V,E)$ with $m$ inputs and $n$ outputs is an _$(m,n)$
-superconcentrator_, if for any equal-size inputs $X\subseteq[m]$ and outputs
$Y\subseteq[n]$, the number of vertex-disjoint paths from $X$ to $Y$ is
$|X|$.) Furthermore, the code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ (encoded by
the above circuits) satisfies a distance criterion, stronger than MDS (maximum
distance separable) codes, captured by the following definition.

######  Definition 5.1.

(Superconcentrator-induced code) $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ is a
_superconcentrator-induced code_ if

$\operatorname{dist}(C(x),C(y))\;\geq\;m-\operatorname{dist}(x,y)+1$

for any distinct $x,y\in\mathbb{F}^{n}$.

For a linear code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$, it is well known that
$C$ is an MDS code, i.e., $C$ satisfies the Singleton bound

$\operatorname{dist}(C(x),C(y))\;\geq\;m-n+1\quad\forall
x\not=y\in\mathbb{F}^{n},$

if and only if any $n$ columns of its generator matrix are linearly
independent. Similarly, we show that a linear code is a superconcentrator-
induced code if and only if every square submatrix of its generator matrix is
nonsingular. (Such matrices are sometimes called _totally invertible
matrices_.)

######  Lemma 5.2.

Linear code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ is a superconcentrator-induced
code if and only if every square submatrix of its generator matrix is
nonsingular.

###### Proof.

For the “if” direction, assume for contradiction that there exists a nonzero
$x\in\mathbb{F}^{n}$ such that $\operatorname{wt}(C(x))\leq
m-\operatorname{wt}(x)$. Let $X=\operatorname{supp}(x)\subseteq[n]$, and let
$Y$ be any subset of $[m]\setminus\operatorname{supp}(C(x))$ of size $|X|$.
Denote the generator matrix by $M\in\mathbb{F}^{n\times m}$. By the definition
of the generator matrix, we have $C(x)=xM$. Thus,

$\displaystyle C(x)|_{Y}\;=\;$ $\displaystyle xM_{[n],Y}$ $\displaystyle\;=\;$
$\displaystyle x|_{X}M_{X,Y}+x|_{[n]\setminus X}M_{[n]\setminus X,Y}$
$\displaystyle\;=\;$ $\displaystyle x|_{X}M_{X,Y}$ $\displaystyle{\text{since
}x|_{[n]\setminus X}=0,}$

where $M_{X,Y}$ denotes the $|X|\times|Y|$ submatrix indexed by rows $X$ and
columns $Y$. Since matrix $M_{X,Y}$ is nonsingular, and $x|_{X}$ is nonzero,
we claim $C(x)|_{Y}$ is nonzero. This contradicts the definition of $Y$.

For the “only if” direction, we prove the contraposition. That is, if there
exists a singular square submatrix, then $C$ is not a superconcentrator-
induced code. Suppose there exist equal-size $X\subseteq[n]$ and
$Y\subseteq[m]$ such that $M_{X,Y}$ is singular. Since
$\operatorname{rank}M_{X,Y}<|X|$, there exists a nonzero
$x^{\prime}\in\mathbb{F}^{|X|}$ such that $x^{\prime}M_{X,Y}=0$. Extend
$x^{\prime}$ to a vector $x\in\mathbb{F}^{n}$ by adding zeros on the
coordinates outside of $X$, that is, $x^{\prime}=x|_{\operatorname{supp}(x)}$.
As such, we have

$\displaystyle C(x)|_{Y}\;=\;$ $\displaystyle(xM)|_{Y}$ $\displaystyle\;=\;$
$\displaystyle xM_{[n],Y}$ $\displaystyle\;=\;$ $\displaystyle
x|_{X}M_{X,Y}+x|_{[n]\setminus X}M_{[n]\setminus X,Y}$ $\displaystyle\;=\;$
$\displaystyle x|_{X}M_{X,Y}$ since $x_{[n]\setminus X}$ is zero
$\displaystyle\;=\;$ $\displaystyle x^{\prime}M_{X,Y}$ $\displaystyle\;=\;$
$\displaystyle 0,$

which implies that $\operatorname{wt}(C(x))\leq m-|Y|=m-\operatorname{wt}(x)$.
That is, $C$ is not a superconcentrator-induced code. ∎

We justify the naming “superconcentrator-induced codes” by proving

  * •

Any (unrestricted) arithmetic circuit encoding a superconcentrator-induced
code, viewed as a graph, must be a superconcentrator.

  * •

Any superconcentrator can be converted to an arithmetic circuit encoding a
superconcentrator-induced code, by replacing each vertex with an addition gate
over a sufficiently large finite field, and choosing the coefficients
uniformly at random. (The field size is exponential in the size of the graph.)

We consider the following unrestricted arithmetic circuit model encoding a
superconcentrator-induced code $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$:

  * •

Let $\mathbb{F}$ be a finite field.

  * •

There are $n$ inputs, denoted by $x_{1},x_{2},\ldots,x_{n}\in\mathbb{F}$;
there are $m$ outputs, denoted by $y_{1},y_{2},\ldots,y_{m}\in\mathbb{F}$.

  * •

Gates have unbounded fanin and fanout. The size of the circuit is defined to
be the number of wires, instead of gates.

  * •

Each internal and output gate can compute _any_ function from
$\mathbb{F}^{s}\to\mathbb{F}$, where $s$ is the fanin of the gate (unbounded).

In this model, any single output function from $\mathbb{F}^{n}$ to
$\mathbb{F}$ can be computed by a single gate. It makes sense to consider the
circuit complexity of multiple output functions.

######  Lemma 5.3.

Any unrestricted arithmetic circuit encoding a superconcentrator-induced code
must be a superconcentrator.

###### Proof.

Let $C:\mathbb{F}^{n}\to\mathbb{F}^{m}$ be an unrestricted arithmetic circuit
encoding a superconcentrator-induced code. Let $G$ denote the underlying
directed acyclic graph with $n$ inputs and $m$ outputs.

Suppose for contradiction that $G$ is not an $(n,m)$-superconcentrator, that
is, there exist equal-size inputs $S\subseteq[n]$ and outputs $T\subseteq[m]$
such that the number of vertex-disjoint paths from $S$ to $T$ is less than
$|S|$. By Menger’s theorem, there exists a cut vertex set, denoted by $V$,
whose removal disconnects $S$ and $T$ and $|V|<|S|$.

Fix the inputs outside of $S$ arbitrarily, while leave the inputs in $S$
undetermined. So, the outputs in $T$ are completely determined by the gates in
$V$, the “cut vertices” between $S$ and $T$. Since $|V|<|S|$, the outputs in
$T$ can take at most $|\mathbb{F}|^{|V|}<|\mathbb{F}|^{|S|}$ values. By the
pigeonhole principle, there exist $x,x^{\prime}\in\mathbb{F}^{n}$ such that

  * •

$x|_{S}\not=x^{\prime}|_{S}$,

  * •

$x|_{[n]\setminus S}=x^{\prime}|_{[n]\setminus S}$, and

  * •

$C(x)|_{T}=C(x^{\prime})|_{T}$.

Therefore, $\operatorname{dist}(C(x),C(x^{\prime}))\leq m-|T|=m-|S|$, and
$\operatorname{dist}(x,x^{\prime})\leq|S|$, which implies
$\operatorname{dist}(C(x),C(x^{\prime}))\leq
m-\operatorname{dist}(x,x^{\prime})$. This contradicts the definition of
superconcentrator-induced codes. ∎

In the reverse direction, we prove the following.

######  Lemma 5.4.

Let $G$ by an $(n,m)$-superconcentrator. Let
$C_{G}:\mathbb{F}^{n}\to\mathbb{F}^{m}$ be an arithmetic circuit by replacing
each vertex in $G$ with an addition gate, and choosing the coefficient on each
edge uniformly and random (over the finite field $\mathbb{F}$). With
probability at least $1-\sum_{i=1}^{n}{n\choose i}{m\choose
i}\frac{di}{|\mathbb{F}|},$ $C_{G}$ encodes a superconcentrator-induced code.

###### Proof.

Denote the inputs by $x_{1},x_{2},\ldots,x_{n}$, and outputs by
$y_{1},y_{2},\ldots,y_{m}$. For each edge $e\in E(G)$, assign a random
coefficient $r_{e}$. Let $M$ be the $n\times m$ generator matrix of the linear
code $C_{G}$. One can see that

$M_{i,j}\;=\;\sum_{\text{path $p$ from $x_{i}$ to $y_{j}$}}\prod_{e\in
E(p)}r_{e},$

where $p$ enumerates _all_ paths from $x_{i}$ to $y_{j}$. View $M_{i,j}$ as a
(multilinear) polynomial in $\mathbb{F}[\\{r_{e}\\}_{e\in E(G)}]$. Note that
the degree of $M_{i,j}$ is exactly the length of the longest path from $x_{i}$
to $y_{j}$.

######  Claim 5.5.

For any equal-size subsets $X\subseteq[n]$ and $Y\subseteq[m]$,

$\Pr[\det(M_{X,Y})=0]\;\leq\;\frac{d|X|}{|\mathbb{F}|},$

where $d$ is the depth of the superconcentrator.

###### Proof.

(of Claim 5.5) Note that $\det(M_{X,Y})$ is a polynomial of degree at most
$d|X|$, since each entry is of degree at most $d$. By the definition of
superconcentrator, there are $|X|$ vertex-disjoint paths connecting $X$ and
$Y$. Setting $r_{e}$ to 1 for all edges $e$ on these $|X|$ vertex-disjoint
paths, and leaving all others 0, the polynomial $\det(M_{X,Y})$ evaluates to
$\pm 1$, which implies that $\det(M_{X,Y})$ is a nonzero polynomial. The claim
follows from the Schwarz-Zipple lemma. ∎

By Lemma 5.2, $C_{G}$ encodes a superconcentrator-induced code if and only if
all square submatrix of $M$ is nonsingular. Taking a union bound over all
equal-size $X\subseteq[n]$ and $Y\subseteq[m]$, we have

$\Pr[C_{G}\text{ encodes a superconcentrator-induced
code}]\;\geq\;1-\sum_{i=1}^{n}{n\choose i}{m\choose
i}\frac{di}{|\mathbb{F}|}.$

∎

##  6 Conclusion

In this work, we determine, up to an additive constant 2, the minimum depth
required to encode asymptotically good error-correcting codes, i.e., codes
with constant rate and constant relative distance, using a linear number of
wires. The minimum depth is between $\alpha(n)-2$ and $\alpha(n)$, where
$\alpha(n)$ is a version of the inverse Ackermann function. The upper bound is
met by certain binary codes we construct (building on Gál _et al._ [Gal+13]
with a few new ingredients) for any constant rate and constant relative
distance within the Gilbert-Varshamov bounds. The lower bound applies to any
constant rate and constant relative distance. We credit the lower bound to Gál
_et al._ [Gal+13], although not explicitly claimed or fully verified in
[Gal+13]; because our contribution is a routine checking of details.

Valiant articulated graph-theoretic arguments for proving circuit lower bounds
[Val75, Val76, Val77]. Since then, there have been fruitful results along this
line. We show a result in the reverse direction, that is, we prove that any
superconcentrator (after being converted to an arithmetic circuit) can encode
a good code over a sufficiently large field (exponential in the size of the
superconcentrator graph).

## References

  * [Ahl+00] Rudolf Ahlswede, Ning Cai, S-YR Li and Raymond W Yeung  “Network information flow”  In _IEEE Transactions on information theory_ 46.4 IEEE, 2000, pp. 1204–1216
  * [AP94] Noga Alon and Pavel Pudlák  “Superconcentrators of depths 2 and 3; odd levels help (rarely)”  In _J. Comput. Syst. Sci._ 48.1, 1994, pp. 194–202
  * [BM05] Louay M.. Bazzi and Sanjoy K. Mitter  “Endcoding complexity versus minimum distance”  In _IEEE Transactions on Information Theory_ 51.6 IEEE, 2005, pp. 2103–2112
  * [BIL12] Chris Beck, Russell Impagliazzo and Shachar Lovett  “Large deviation bounds for decision trees and sampling lower bounds for AC0 circuits”  In _Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on_ , 2012, pp. 101–110  IEEE
  * [Bop97] Ravi B. Boppana  “The average sensitivity of bounded-depth circuits”  In _Information Processing Letters_ 63.5, 1997, pp. 257–261
  * [CT19] Lijie Chen and Roei Tell  “Bootstrapping results for threshold circuits “just beyond” known lower bounds”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , 2019, pp. 34–41
  * [CKL13] Ho Yee Cheung, Tsz Chiu Kwok and Lap Chi Lau  “Fast matrix rank algorithms and applications”  In _Journal of the ACM (JACM)_ 60.5 ACM New York, NY, USA, 2013, pp. 1–25
  * [CW89] Aviad Cohen and Avi Wigderson  “Dispersers, deterministic amplification, and weak random sources”  In _30th Annual Symposium on Foundations of Computer Science_ , 1989, pp. 14–19  IEEE Computer Society
  * [DGP73] Roland L. Dobrushin, S.. Gelfand and Mark S. Pinsker  “On complexity of coding”  In _Proc. 2nd Internat. Symp. on Information Theory_ , 1973, pp. 174–184
  * [Dol+83] Danny Dolev, Cynthia Dwork, Nicholas Pippenger and Avi Wigderson  “Superconcentrators, generalizers and generalized connectors with limited depth”  In _Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA_ ACM, 1983, pp. 42–51
  * [DI14] Erez Druk and Yuval Ishai  “Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications”  In _Proceedings of the 5th conference on Innovations in theoretical computer science_ , 2014, pp. 169–182
  * [Gal+13] Anna Gal, Kristoffer Arnsfelt Hansen, Michal Koucky, Pavel Pudlak and Emanuele Viola  “Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates”  In _IEEE Transactions on Information Theory_ 59.10 IEEE Press, 2013, pp. 6611–6627
  * [Gol+21] Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler and Riad S Wahby  “Brakedown: Linear-time and post-quantum SNARKs for R1CS”  In _Cryptology ePrint Archive_ , 2021
  * [GRS12] Venkatesan Guruswami, Atri Rudra and Madhu Sudan  “Essential coding theory”  In _Draft available at http://www. cse. buffalo. edu/atri/courses/coding-theory/book_ 2.1, 2012
  * [Ish+08] Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai  “Cryptography with constant computational overhead”  In _Proceedings of the fortieth annual ACM symposium on Theory of computing_ , 2008, pp. 433–442
  * [LYC03] S-YR Li, Raymond W Yeung and Ning Cai  “Linear network coding”  In _IEEE transactions on information theory_ 49.2 IEEE, 2003, pp. 371–381
  * [Li17] Yuan Li  “Some Results in Low-Depth Circuit Complexity”  The University of Chicago, 2017
  * [Li23] Yuan Li  “Secret Sharing on Superconcentrator”  In _arXiv preprint arXiv:2302.04482_ , 2023
  * [LX04] San Ling and Chaoping Xing  “Coding theory: a first course”  Cambridge University Press, 2004
  * [Lov18] Shachar Lovett  “MDS matrices over small fields: A proof of the GM-MDS conjecture”  In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_ , 2018, pp. 194–199  IEEE
  * [LV11] Shachar Lovett and Emanuele Viola  “Bounded-depth circuits cannot sample good codes”  In _Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on_ , 2011, pp. 243–251  IEEE
  * [Pud94] Pavel Pudlak  “Communication in bounded depth circuits”  In _Combinatorica_ 14.2 Springer, 1994, pp. 203–216
  * [RT00] Jaikumar Radhakrishnan and Amnon Ta-Shma  “Bounds for dispersers, extractors, and depth-two superconcentrators”  In _SIAM Journal on Discrete Mathematics_ 13.1 SIAM, 2000, pp. 2–24
  * [RS03] Ran Raz and Amir Shpilka  “Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates”  In _SIAM J. Comput._ 32.2, 2003, pp. 488–513  DOI: 10.1137/S009753970138462X
  * [Sip88] Michael Sipser  “Expanders, randomness, or time versus space”  In _Journal of Computer and System Sciences_ 36.3 Elsevier, 1988, pp. 379–383
  * [SS96] Michael Sipser and Daniel A Spielman  “Expander codes”  In _IEEE transactions on Information Theory_ 42.6 IEEE, 1996, pp. 1710–1722
  * [Spi96] Daniel A Spielman  “Linear-time encodable and decodable error-correcting codes”  In _IEEE Transactions on Information Theory_ 42.6 IEEE, 1996, pp. 1723–1731
  * [Tar75] Robert Endre Tarjan  “Efficiency of a good but not linear set union algorithm”  In _Journal of the ACM (JACM)_ 22.2 ACM New York, NY, USA, 1975, pp. 215–225
  * [Val75] Leslie G Valiant  “On non-linear lower bounds in computational complexity”  In _Proceedings of the seventh annual ACM symposium on Theory of computing_ , 1975, pp. 45–53
  * [Val76] Leslie G Valiant  “Graph-theoretic properties in computational complexity”  In _Journal of Computer and System Sciences_ 13.3 Academic Press, 1976, pp. 278–285
  * [Val77] Leslie G. Valiant  “Graph-theoretic arguments in low-level complexity”  In _Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings_ , 1977, pp. 162–176
  * [Vio19] Emanuele Viola  “Lower bounds for data structures with space close to maximum imply circuit lower bounds”  In _Theory of Computing_ 15.1 Theory of Computing Exchange, 2019, pp. 1–9

##  Appendix A Properties of the inverse Ackermann-type functions

######  Proposition A.1.

(Claim 2.4 in [RS03])

* [1] [(i).] Each $\lambda_{i}(n)$ is a monotone function tending to infinity with $n$.
* [2] [(ii).] For $i\geq 2$, $\lambda_{2i+1}(n)\leq\lambda_{2i}(n)\leq 2\lambda_{2i+1}(n)$.
* [3] [(iii).] For $i\geq 2$ and $n\geq 2^{7}$, $\lambda_{i}(n)\leq\lfloor\sqrt{\frac{n}{2}}\rfloor$.

The following proposition is given as Proposition 2 and 3 in the subsequent
paper [Li23], but was developed first in the present work.

######  Proposition A.2.

  * (i)

For any $d\geq 1$, and for all $n\geq 4$,

$\lambda_{d}(n)\;\leq\;n-2.$

  * (ii)

For any $d\geq 1$,

$\lambda_{d}(d)\;\leq\;4.$

###### Proof.

(i) We prove by induction on $d$. When $d=1$ or $2$, it is easy to verify that
$\lambda_{d}(n)\leq n-2$. Assuming $\lambda_{d}(n)\leq n-2$ for all $n\geq 4$,
let us prove that $\lambda_{d+2}(n)\leq n-2$. By the definition of
$\lambda_{d+2}(n)$, we have

$\lambda_{d+2}(n)\;=\;\lambda_{d}^{*}(n)\;\leq\;\lambda_{d}(n)\;\leq\;n-2.$

(ii) We prove by induction on $d$. When $d\leq 3$, it is easy to verify by
straightforward calculation. Assuming $\lambda_{d}(d)\leq 4$ is true for $d$,
where $d\geq 2$, let us prove $\lambda_{d+2}(d+2)\leq 4$. We have

$\displaystyle\lambda_{d+2}(d+2)\;\;=\;\;$ $\displaystyle\lambda_{d}^{*}(d+2)$
$\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{d}^{*}\left(\lambda_{d}(d+2)\right)+1$
$\displaystyle\;\;\leq\;\;$ $\displaystyle\lambda_{d}^{*}(d)+1$ Proposition
A.2 (i) $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{d}^{*}(\lambda_{d}(d))+2$ $\displaystyle\;\;\leq\;\;$
$\displaystyle\lambda_{d}^{*}(4)+2$ By induction hypothesis
$\displaystyle\;\;\leq\;\;$
$\displaystyle\max\\{\lambda^{*}_{2}(4),\lambda^{*}_{3}(4)\\}+2$
$\displaystyle\;\;=\;\;$ $\displaystyle 4.$

∎

######  Proposition A.3.

For any $i,d\geq 1$,

  * (1).

$A(i+1,d)=A^{(d)}_{i}(1)$.

  * (2).

$\lambda_{2i}(A(i,d))=d$.

  * (3).

$\lambda_{2i}(A(i,d)+1)=d+1$.

  * (4).

$A(i,d)=\max\\{n:\lambda_{2i}(n)\leq d\\}.$

  * (5).

$A(i,\lambda_{2i}(d))\geq d$.

###### Proof.

(1). By Definition 2.3,

$\displaystyle A(i+1,d)$ $\displaystyle=$ $\displaystyle A(i,A(i+1,d-1))$
$\displaystyle=$ $\displaystyle A(i,A(i,A(i+1,d-2)))$ $\displaystyle=$
$\displaystyle\underbrace{A(i,A(i,\ldots}_{d-1\text{ times}},A(i+1,1)\ldots))$
$\displaystyle=$ $\displaystyle A_{i}^{(d)}(1),$

where we write $A(i,j)$ as $A_{i}(j)$.

(2). Prove by induction on $i$. For the base case $i=1$, we have
$A(1,d)=2^{d}$, and $\lambda_{2}(n)=\lceil\log_{2}n\rceil$. It is obvious that
the $\lambda_{2}(A(1,d))=d$ holds.

For the induction step, assuming the conclusion holds for $i$, let us prove it
for $i+1$.

$\displaystyle\lambda_{2(i+1)}(A(i+1,d))$ $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d)}_{i}(1)\right)$
$\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d-1)}_{i}(1)\right)+1$ By induction
hypothesis $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d-2)}_{i}(1)\right)+2$ By induction
hypothesis $\displaystyle\vdots$ $\displaystyle\;\;=\;\;$ $\displaystyle d.$

(3). Prove by induction on $i$. For the base case $i=1$, we have
$A(1,d)=2^{d}$, and $\lambda_{2}(n)=\lceil\log_{2}n\rceil$. It is obvious that
the $\lambda_{2}(A(1,d)+1)=d+1$ holds.

For the induction step, assuming the conclusion holds for $i$, let us prove it
for $i+1$.

$\displaystyle\lambda_{2(i+1)}(A(i+1,d)+1)$ $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d)}_{i}(1)+1\right)$
$\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A\left(i,A^{(d-1)}_{i}(1)\right)+1\right)$
$\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d-1)}_{i}(1)+1\right)+1$ By induction
hypothesis $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}\left(A^{(d-2)}_{i}(1)+1\right)+2$ By induction
hypothesis $\displaystyle\vdots$ $\displaystyle\;\;=\;\;$
$\displaystyle\lambda_{2i}^{*}(1+1)+d$ $\displaystyle\;\;=\;\;$ $\displaystyle
d+1.$

(4) follows from (2) and (3).

(5) follows from (4). ∎

######  Proposition A.4.

Let $c>0$ be a constant. When $d$ is large enough, $\lambda_{d}(c\cdot
d2^{d/2})\leq d$.

###### Proof.

If $d$ is even, i.e., $d=2i$, by Proposition A.3, it suffices to prove

$c(2i)2^{i}\;\leq\;A_{i}(2i).$ (12)

Notice that $A_{1}(2i)=2^{2i}$ and $A_{i+1}(n)\geq A_{i}(n)$. Clearly, (12) is
true when $i$ is large enough, and this sufficiently large number only depends
on $c$.

If $d$ is odd, i.e., $d=2i+1$, it suffices to prove $\lambda_{2i}(c\cdot
d2^{d/2})\leq d$, as $\lambda_{2i+1}(n)\leq\lambda_{2i}(n)$ by Proposition
A.1. By Proposition A.3, it suffices to prove

$c(2i+1)2^{i+\frac{1}{2}}\;\leq\;A_{i}(2i+1),$

which is true because $A_{1}(2i+1)=2^{2i+1}$. ∎

##  Appendix B Proof of Theorem 4.3

######  Lemma B.1.

(Lemma 8 in [Pud94]) For any $1\leq r\leq n$, and for any
$\epsilon,\delta\in(0,1]$, we have

$D\left(n,1,\epsilon,\delta,\frac{1}{r}\right)\;\geq\;\epsilon\delta^{2}nr.$

######  Lemma B.2.

(Lemma 5 in [Pud94]) Suppose $f(0)=f(1)=0$ and
$f(n)\leq\lfloor\sqrt{n}\rfloor$ for every $n>1$. For every $n\geq 0$, we have

  * (i)

$f^{*}(n)\leq f(n)\leq\lfloor\sqrt{n}\rfloor,$

  * (ii)

$\frac{f^{(i)}(n)}{f^{(i+1)}(n)}\geq f^{(i+1)}(n)$ for every $i\geq 1$
provided the denominator is not 0,

  * (iii)

$f^{(i)}(n)\geq\frac{f^{*}(n)}{2}$ for every $i\leq\frac{f^{*}(n)}{2}$.

Indeed, (iii) can be strengthened.

######  Lemma B.3.

Suppose $f(n)\leq\lfloor\sqrt{n}\rfloor$. For every $n\geq 1$ and every
$i\leq\frac{f^{*}(n)}{2}$, we have $f^{(i)}(n)\geq f^{*}(n)$.

###### Proof.

Let us assume $f^{*}(n)\geq 2$. Otherwise, $f^{*}(n)\leq 1$, that is,
$f(n)\leq 1$. Note that $i\leq f^{*}(n)/2\leq 1/2$, and thus $i=0$. So
$f^{(0)}(n)=n\geq f^{*}(n)=1$ always holds.

By the definition of $f^{*}(n)$ and $f(n)\leq\lfloor\sqrt{n}\rfloor$, we have

$\displaystyle f^{(f^{*}(n))}(n)$ $\displaystyle=$ $\displaystyle 1,$
$\displaystyle f^{(f^{*}(n)-1)}(n)$ $\displaystyle\geq$ $\displaystyle 2,$
$\displaystyle f^{(f^{*}(n)-2)}(n)$ $\displaystyle\geq$ $\displaystyle 2^{2},$
$\displaystyle f^{(f^{*}(n)-3)}(n)$ $\displaystyle\geq$ $\displaystyle 2^{4},$
$\displaystyle\ldots$ $\displaystyle f^{(f^{*}(n)-j)}(n)$ $\displaystyle\geq$
$\displaystyle 2^{2^{j-1}}$

for any $1\leq j\leq f^{*}(n)$.

When $i\leq\frac{f^{*}(n)}{2}$, $f^{*}(n)-i\geq\frac{f^{*}(n)}{2}$. Thus,

$\displaystyle f^{(i)}(n)$ $\displaystyle\geq$ $\displaystyle
2^{2^{f^{*}(n)-i-1}}$ $\displaystyle\geq$ $\displaystyle
2^{2^{\frac{f^{*}(n)}{2}-1}}$ $\displaystyle\geq$ $\displaystyle f^{*}(n),$

where the last step is because $2^{2^{\frac{x}{2}-1}}\geq x$ for all real
$x\geq 4$. (If $f^{*}(n)=2$, then $f^{(1)}(n)\geq 2$. If $f^{*}(n)=3$, then
$f^{(1)}(n)\geq 4$.) ∎

The following lemma is proved by Pudlák [Pud94]. To apply it for super-
constant depth, we explicitly determine an appropriate $\beta$ (in terms of
$\alpha$ and $\epsilon,\delta$). We reproduce the proof here.

######  Lemma B.4.

(Lemma 9 in [Pud94]) Let $f(n)\leq\lfloor\sqrt{n}\rfloor$ for every $n$. For
every positive reals $\alpha,\beta,\epsilon$ such that if

$\forall n\forall r\leq n\quad
D\left(n,d,\frac{\epsilon}{2},\delta,\frac{1}{r}\right)\,\geq\,\alpha nf(r),$
(13)

then

$\forall n\forall r\leq n\quad
D\left(n,d+2,\epsilon,\delta,\frac{1}{r}\right)\,\geq\,\beta nf^{*}(r),$ (14)

where $\beta=\min\left\\{\frac{\epsilon\delta}{27},\alpha\right\\}$.

###### Proof.

Let $G$ be a depth-$(d+2)$ layered graph with $n$ inputs and $n$ outputs which
is $(\frac{\epsilon}{2},\delta,\frac{1}{r})$-densely regular. Let $V_{i}$,
$i=0,1,\ldots,d+2$, be the $i$th level of $G$, where $V_{0}$ are inputs and
$V_{d+2}$ are outputs. Let

$A_{0}\,=\,\left\\{v\in V_{1}\cup V_{d+1}:\deg(v)>f(r)\right\\},$

and

$A_{i}\,=\,\left\\{v\in V_{1}\cup
V_{d+1}:\deg(v)\in(f^{(i+1)}(r),f^{(i)}(r)]\right\\}$

for $i=1,2,\ldots,f^{*}(r)$.

######  Claim B.5.

For every $i$, where $1\leq i\leq\frac{f^{*}(r)}{2}-3$, at least one of the
following inequalities holds:

$|A_{0}\cup\cdots\cup
A_{i-1}|\,\geq\,\frac{\epsilon}{4}\cdot\frac{n}{f^{(i+1)}(r)};$ (15)
$|\\{(u,v):(u,v)\text{ incident with }A_{i}\cup A_{i+1}\cup
A_{i+2}\\}|\,\geq\,\frac{\epsilon\delta}{4}n;$ (16) $|\\{(u,v):(u,v)\text{ not
incident with }A_{0}\cup\cdots\cup A_{i+2}\\}|\,\geq\,\alpha
n\frac{f^{(i+2)}(r)}{f^{(i+3)}(r)}n.$ (17)

###### Proof.

(of Claim B.5) The proof is reproduced from [Pud94]. For any
$i\in[1,\frac{f^{*}(r)}{2}-3]$, suppose neither (15) nor (16) is true, we
prove (17).

Let $k\in\left[\frac{n}{f^{(i+1)}(r)},n\right]$ be an arbitrary integer. Let
$\mathcal{X},\mathcal{Y}$ be probability distributions on $k$-element subsets
of inputs and outputs respectively satisfying the condition in Definition 4.1.
Let $X\in\mathcal{X}$, $Y\in\mathcal{Y}$ be random subsets of inputs and
outputs of size $k$.

By the definition of densely regular graphs, there are at least $\epsilon k$
vertex-disjoint paths connecting them. Out of these, there are at most
$\frac{\epsilon}{4}\cdot\frac{n}{f^{(i+1)}(r)}\leq\frac{\epsilon}{4}\cdot k$
paths passing through $A_{0}\cup\cdots\cup A_{i-1}$ by non (15). On _average_
, there are at most $\frac{\epsilon}{4}\cdot k$ paths passing through
$A_{i}\cup A_{i+1}\cup A_{i+2}$, since the expected number of vertices of
$X\cup Y$ directly connected with with $A_{i}\cup A_{i+1}\cup A_{i+2}$ is at
most $\frac{k}{\delta n}\cdot\frac{\epsilon\delta}{4}n=\frac{\epsilon}{4}\cdot
k$. So, on average, the number of vertex-disjoint paths from $X$ to $Y$
avoiding $A_{0}\cup\cdots\cup A_{i+2}$ is at least $\frac{\epsilon}{2}\cdot
k$.

We transform $G$ into a depth-$d$ graph as follows:

  * •

Omit the vertices in $V_{1}$ and $V_{d+1}$.

  * •

For each pair of edges $(u,v),(v,w)$, where $v\in A_{i+3}\cup
A_{i+4}\cup\cdots$, add the edge $(v,w)$.

As such, the size of the new graph, denoted by $G^{\prime}$, is at most
$f^{(i+3)}(r)$ times larger than the size of $G$, since $f^{(i+3)}(r)$ is an
upper bound on the degrees of vertices in $A_{i+3}\cup A_{i+4}\cup\cdots$. We
have shown that $G^{\prime}$ is
$(\frac{\epsilon}{2},\delta,\frac{1}{f^{(i+1)}(r)})$-densely regular. By the
assumption of the lemma, $G^{\prime}$ is of size at least

$D\left(n,d,\frac{\epsilon}{2},\delta,\frac{1}{f^{(i+1)}(r)}\right)\,\geq\,\alpha
nf(f^{(i+1)}(r))\,=\,\alpha nf^{(i+2)}(r),$

which implies that the number of edges not incident with $A_{0}\cup\cdots\cup
A_{i+2}$ is at least

$\frac{|E(G^{\prime})|}{f^{(i+3)}(r)}\,\geq\,\alpha
n\frac{f^{(i+2)}(r)}{f^{(i+3)}(r)}n,$

where the last step is by Lemma B.2 (ii). ∎

Consider the three cases according to Claim B.5.

Case 1: For _some_ $i$, where $1\leq i\leq\frac{f^{*}(r)}{2}-3$, (15) holds.
Since each vertex in $A_{0}\cup\ldots\cup A_{i-1}$ has degree at least
$f^{(i)}(r)$, we have

$\displaystyle|E(G)|\;\;\geq\;\;$
$\displaystyle\frac{\epsilon}{4}\cdot\frac{n}{f^{(i+1)}(r)}\cdot f^{(i)}(r)$
$\displaystyle\;\;\geq\;\;$ $\displaystyle\frac{\epsilon}{4}\cdot n\cdot
f^{(i+1)}(r)$ By Lemma B.2 (ii) $\displaystyle\;\;\geq\;\;$
$\displaystyle\frac{\epsilon}{4}\cdot n\cdot f^{*}(r)$ $\displaystyle\text{By
Lemma \ref{lem:f_star}}.$

Case 2: For _all_ $i$, where $1\leq i\leq\frac{f^{*}(r)}{2}-3$, (16) holds. If
$f^{*}(r)\geq 54$, we have

$\displaystyle|E(G)|\;\;\geq\;\;$
$\displaystyle\frac{1}{3}\cdot\left(\frac{f^{*}(r)}{2}-3\right)\cdot\frac{\epsilon\delta}{4}n$
$\displaystyle\;\;\geq\;\;$
$\displaystyle\frac{1}{3}\cdot\frac{4}{9}f^{*}(r)\cdot\frac{\epsilon\delta}{4}n$
$\displaystyle\;\;=\;\;$ $\displaystyle\frac{1}{27}f^{*}(r)\epsilon\delta n.$

If $f^{*}(r)<54$, we still have $|E(G)|\geq\frac{1}{27}\cdot
f^{*}(r)\epsilon\delta n$ by Claim B.6.

######  Claim B.6.

Let $G$ be a layered graph with $n$ inputs and $n$ outputs and of depth at
least 2, which is $(\epsilon,\delta,\frac{1}{r})$-densely regular. Then
$|E(G)|\geq 2\epsilon\delta n$.

###### Proof.

(of the claim) Let $k\in[\frac{n}{r},n]$. Denote the inputs of $G$ by $I(G)$,
and the outputs of $G$ by $O(G)$. Let $\Delta_{G}(X,Y)$ denote the number of
vertex-disjoint paths between $X$ and $Y$.

By the definition of densely regular graphs, there are nonempty sets of
$k$-element subsets $\mathcal{X}\in{I(G)\choose k}$ and
$\mathcal{Y}\in{O(G)\choose k}$ such that for every $i\in I(G)$, for every
$j\in O(G)$, $\Pr_{X\in\mathcal{X}}[i\in X]\leq\frac{k}{\delta n}\text{ and
}\Pr_{Y\in\mathcal{Y}}[j\in Y]\leq\frac{k}{\delta n}$, and
$\mathbb{E}[\Delta_{G}(X,Y)]\geq\epsilon k$. On the other hand,

$\displaystyle\mathop{\mathbb{E}}_{X\in\mathcal{X}\atop
Y\in\mathcal{Y}}\left[\Delta_{G}(X,Y)\right]\;\;\leq\;\;$
$\displaystyle\mathop{\mathbb{E}}_{X\in\mathcal{X}}[\sum_{x\in\mathcal{X}}\mathbbm{1}_{\deg(x)>0}]$
$\displaystyle\;\;\leq\;\;$ $\displaystyle\sum_{x\in I(G)\text{ and
}\deg(x)>0}\Pr_{x\in\mathcal{X}}[x\in\mathcal{X}]$ $\displaystyle\;\;\leq\;\;$
$\displaystyle\frac{k}{\delta n}\sum_{x\in I(G)}\deg(x).$

Putting them together, we have $\sum_{x\in I(G)}\deg(x)\geq\epsilon\delta n$.
Similarly, we can prove $\sum_{y\in O(G)}\deg(y)\geq\epsilon\delta n$. Since
$G$ is a layered graph of depth at least 2, we have $|E(G)|\geq
2\epsilon\delta n$. ∎

Case 3: For _some_ $i$, where $1\leq i\leq\frac{f^{*}(r)}{2}-3$, (17) holds.
So we have

$|E(G)|\,\geq\,\alpha n\frac{f^{(i+2)}(r)}{f^{(i+3)}(r)}n\,\geq\,\alpha
f^{(i+3)}(r)\,\geq\,\alpha nf^{*}(r).$

Combining 3 cases, we have
$\beta=\min\left\\{\frac{\epsilon}{4},\frac{\epsilon\delta}{27},\alpha\right\\}=\min\left\\{\frac{\epsilon\delta}{27},\alpha\right\\}$.
∎

We are ready to prove Theorem 4.3.

###### Proof.

(of Theorem 4.3) Since $\lambda_{2i}(n)=\Theta(\lambda_{2i+1}(n))$ for $i\geq
2$, it suffices to prove

$D\left(n,2d+1,\epsilon,\delta,\frac{1}{r}\right)\,\geq\,\min\left\\{\frac{1}{27},\frac{\delta}{2}\right\\}2^{-d}\epsilon\delta
n\lambda_{2d+1}(r).$ (18)

The base case for $d=0$ is proved in Lemma B.1. Assume (18) is true for $d$,
let us prove it for $d+1$. By induction hypothesis, we have

$D\left(n,2d+1,\frac{\epsilon}{2},\delta,\frac{1}{r}\right)\,\geq\,\min\left\\{\frac{1}{27},\frac{\delta}{2}\right\\}2^{-(d+1)}\epsilon\delta
n\lambda_{2d+1}(r)$

holds for any $r\leq n$. By Lemma B.4, we have
$D(n,2d+3,\epsilon,\delta,\frac{1}{r})\geq\beta n\lambda_{2d+1}^{*}(r)=\beta
n\lambda_{2d+3}(r),$ where

$\displaystyle\beta$ $\displaystyle=$
$\displaystyle\min\left\\{\frac{\epsilon\delta}{27},\min\left\\{\frac{1}{27},\frac{\delta}{2}\right\\}2^{-(d+1)}\epsilon\delta\right\\}$
$\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{27},\frac{\delta}{2}\right\\}2^{-(d+1)}\epsilon\delta,$

which completes the induction step. ∎