###  5.1 Layered-Polynomial Representation

The first step is to “arithmetize” our low-depth circuit into a _layered-
polynomial representation_. Roughly speaking, given a (uniform) circuit $C$ of
depth $d$ and size $T$, we will produce a table of size $d^{\prime}\times
T^{\prime}$ where $d^{\prime}\approx d$ and $T^{\prime}=\mathrm{poly}(T)$,
such that the following key properties hold:

  * (Low-degree.)

Each row is the “truth table” of a low-degree polynomial (thus admits self-
correction properties).

  * (Faithful representation.)

Given oracle access to the $d^{\prime}$-th row, we can compute the output of
$C(1^{n})$ quickly.

  * (Downward self-reducibility.)

For each $2\leq i\leq d^{\prime}$, given oracle access to the $(i-1)$-th
polynomial, we can quickly compute the output of the $i$-th polynomial on a
given input. Moreover, the entries of the first row (corresponding to $i=1$)
can be computed quickly.

Later, we will use these properties of the layered-polynomial representation
to compile them into a reconstructive HSG.

We now formally describe our layered-polynomial representation, which can be
proved by modifying the construction in [CT21]. In the following, letting $p$
be a power of $2$, and
$f\colon\mathbb{F}_{p}^{\ell}\rightarrow\mathbb{F}_{p}$, we use
$\mathtt{tt}(f)$ to denote the length-$(p^{\ell}\cdot\log p)$ Boolean string
that consists of $p^{\ell}$ blocks, where the $i$-th block corresponds to the
Boolean encoding of the $i$-th element in $\mathbb{F}_{p}$.

######  Theorem 5.1 (Layered-Polynomial Representation).

There exist universal constants $c,c^{\prime},\beta>1$ such that the following
holds. Let $\kappa\in\mathbb{N}$ and let $T,d,n,h,p\in\mathbb{N}$ all be
sufficiently large such that _(1)_ $d\leq T$ and $n\leq T$, and _(2)_ $h,p$
are both nice powers of $2$ and $\log T\leq h<p\leq h^{27}\leq T$. _(_ Recall
that $p$ is a nice power of $2$ if $p=2^{2\cdot 3^{\lambda}}$ for some
$\lambda\in\mathbb{N}$._)_

Let $\vec{\ell}\triangleq(\kappa,T,d,n,h,p)$ be the input parameters, and let
$\mathbb{F}\triangleq\mathbb{F}_{p}$. For a Turing machine $\mathsf{TM}$ with
description size $|\mathsf{TM}|=\kappa\cdot\log T$, let

$C_{\mathsf{TM}}\triangleq\mathsf{Circuit}[T,\kappa\cdot\log
T,n,n](\mathsf{TM}).$

Assuming $C_{\mathsf{TM}}\neq\bot$ and $C_{\mathsf{TM}}$ has depth at most
$d$, there are $d^{\prime}\triangleq
c\kappa\cdot\log^{2}T\cdot(d+\kappa^{2}\log T)$ polynomials
$\left(P_{i}^{\vec{\ell},\mathsf{TM}}\right)_{i\in[d^{\prime}]}$ such that the
following hold _(_ below we write $P_{i}^{\vec{\ell},\mathsf{TM}}$ as $P_{i}$
for simplicity _)_ :

  1. 1.

(Arithmetic setting.) Let $H\subset\mathbb{F}$ be the first $h$ elements of
$\mathbb{F}$, and let $m$ be the smallest power of $3$ such that $h^{m}\geq
T^{\beta\kappa}$. Each polynomial is from $\mathbb{F}^{3m}$ to $\mathbb{F}$
and has total degree at most $\Delta=c\cdot h\cdot\log^{3}(T)$.

  2. 2.

(Faithful representation.) Fix an injective function
$\mathsf{id}\colon[n]\rightarrow H^{m}$ in an arbitrary but canonical
way.212121For simplicity, we will ignore the complexity of computing
$\mathsf{id}$ and its inverse since it is negligible. For every $i\in[n]$,
$\left(C_{\mathsf{TM}}(1^{n})\right)_{i}=P_{d^{\prime}}(\mathsf{id}(i),0^{2m})$.

  3. 3.

(Complexity of the polynomials.) Let $T_{\sf poly}\triangleq T^{c\cdot\kappa}$
and $d_{\sf poly}\triangleq c\cdot(d\log T+\kappa^{2}\log^{2}T)$. There is a
Turing machine $\mathsf{TM}_{\sf poly}$ of description length $\log T_{\sf
poly}$ such that for

$C_{\sf poly}\triangleq\mathsf{Circuit}\left[T_{\sf poly},\log T_{\sf
poly},\log
d^{\prime},|\mathbb{F}|^{3m}\cdot\log|\mathbb{F}|\right](\mathsf{TM}_{\sf
poly}),$

it holds that _(1)_ for every $i\in[d^{\prime}]$ $C_{\sf
poly}(i)=\mathtt{tt}(P_{i})$ and _(2)_ $C_{\sf poly}$ has depth $d_{\sf
poly}$.

Moreover, there is a polynomial-time algorithm $\mathbb{A}^{\sf
poly}_{\vec{\ell}}$ that takes $\mathsf{TM}\in\\{0,1\\}^{\kappa\log T}$ as
input, and outputs the description of $\mathsf{TM}_{\sf poly}$.

  4. 4.

(Downward self-reducibility.) There is a $\max(n,h)\cdot h^{c^{\prime}}$-time
algorithm $\mathsf{Base}$ that takes inputs $\vec{\ell}$,
$\mathsf{TM}\in\\{0,1\\}^{\kappa\cdot\log T}$, and
$\vec{w}\in\mathbb{F}^{3m}$, outputs $P_{1}(\vec{w})$.

Also, there is an $h^{c^{\prime}}$-time oracle algorithm $\mathsf{DSR}$ that
takes inputs $\vec{\ell}$, $\mathsf{TM}\in\\{0,1\\}^{\kappa\cdot\log T}$,
$i\in\\{2,\dotsc,d^{\prime}\\}$, and $\vec{w}\in\mathbb{F}^{3m}$, and oracle
access to a polynomial
$\widetilde{P}\colon\mathbb{F}^{3m}\rightarrow\mathbb{F}$, such that when it
is given $P_{i-1}$ as the oracle, it outputs $P_{i}(\vec{w})$.

###### Proof.

Recall that we use $\vec{\ell}$ to denote the input parameters
$(\kappa,T,d,n,h,p)$. We will follow the proof of [CT21, Proposition 4.7],
which in turn follows [Gol17] (see also [Gol18]). In the following, we will
simply use $C$ to denote the (low-depth) circuit
$C_{\mathsf{TM}}=\mathsf{Circuit}\left[T,\kappa\cdot\log
T,n,n\right](\mathsf{TM})$ for notational convenience, but we stress that $C$
depends on both $\vec{\ell}$ and $\mathsf{TM}$ (and so does the later circuits
constructed from $C$).

####  5.1.1 Construction of a Highly Uniform Circuit $D$

We first construct a circuit $D$ that has better uniformity and preserves the
functionality of $C$, i.e., $D(1^{n})=C(1^{n})$. Given input $1^{n}$, $D$
first computes a description of $C=\mathsf{Circuit}\left[T,\kappa\cdot\log
T,n,n\right](\mathsf{TM})$ (represented as a $T\times T\times T$ tensor) and
then computes the $\mathsf{Eval}$ function $\langle\langle
C\rangle,n,d\rangle\mapsto C(1^{n})$. Let $s\triangleq\kappa\cdot\log T$ and
$s^{\prime}\triangleq O(s+\log(3\log T))$ be such that each configuration of
$\mathsf{TM}$ on $3\log T$-bit inputs can be described by $s^{\prime}$ bits.

The circuit $D$ is constructed by composing the following three subcircuits.
Let $\mu\in\mathbb{N}$ be a sufficiently large universal constant. We will
describe and analyze their complexities (or state the complexity bounds proved
in [CT21, Gol17]).

  1. 1.

(Computing the adjacency matrices for configurations.) The first circuit
$D^{(1)}$ takes $n$ bits as input (which are supposed to be $1^{n}$), outputs
a list of $T^{3}$ matrices from $\\{0,1\\}^{2^{s^{\prime}}\times
2^{s^{\prime}}}$, such that the $(u,v,w)$-th matrix222222We use
$(u,v,w)\in[T]^{3}$ to denote the integer $(u-1)T^{2}+(v-1)T+w\in[T^{3}]$.
$M^{(u,v,w)}$ satisfies the following condition: for every
$\gamma,\gamma^{\prime}\in\\{0,1\\}^{s^{\prime}}$,
$M^{(u,v,w)}[\gamma,\gamma^{\prime}]=1$ if and only if $\mathbb{A}_{\sf
nxt}(\mathsf{TM},s,(u,v,w),\gamma,\gamma^{\prime})$ (i.e., $\gamma^{\prime}$
is the configuration obtained by running $\mathsf{TM}$ for one step on
configuration $\gamma$ and input $(u,v,w)$ with space bound $s$). Recall we
assumed that if $\gamma$ is the accepting or the rejecting configuration, then
its next configuration is $\gamma$ itself.

Complexity of $D^{(1)}$. $D^{(1)}$ can be implemented by a projection (i.e.,
depth $d_{D^{(1)}}=2$ and size $T_{D^{(1)}}=T^{3}\cdot
2^{2s^{\prime}}$).232323Note that we can implement projections and
restrictions of input bits to $0$ and $1$ using two layers of $\mathsf{NAND}$
gates. Moreover, from 2.2, given $\vec{\ell}$ and $\mathsf{TM}$, in polynomial
time we can compute a Turing machine
$\mathsf{TM}_{D^{(1)}}\in\\{0,1\\}^{(\kappa+\mu)\cdot\log T}$ such that

$\mathsf{Circuit}\left[T_{D^{(1)}},s_{D^{(1)}},n,T^{3}\cdot
2^{2s^{\prime}}\right]\left(\mathsf{TM}_{D^{(1)}}\right)=D^{(1)},$

where $s_{D^{(1)}}=\mu\cdot s^{\prime}$.

  2. 2.

(Computing the adjacency relation tensor of $C$ via matrix multiplication.)
The second circuit $D^{(2)}$ takes a list of $T^{3}$ matrices from
$\\{0,1\\}^{2^{s^{\prime}}\times 2^{s^{\prime}}}$ as input, and outputs a
tensor from $\\{0,1\\}^{T\times T\times T}$ followed by the encoding of a pair
$(n,d)$.

In more detail, given the output of $D^{(1)}(1^{n})$, for every
$(u,v,w)\in[T]^{3}$, it determines whether $\mathsf{TM}(u,v,w)=1$ by computing
$(M^{(u,v,w)})^{2^{s^{\prime}}}$, which can be done by repeated squaring
$s^{\prime}$ times. This gives the adjacent relation tensor of $C$.

Complexity of $D^{(2)}$. $D^{(2)}$ can be implemented by a circuit of depth
$d_{D^{(2)}}=\mu\cdot(s^{\prime})^{2}$ and size $T_{D^{(2)}}=T^{3}\cdot 2^{\mu
s^{\prime}}$. Moreover, from [CT21, Gol17] (note that $D^{(2)}$ does not
depend on $\mathsf{TM}$), given $\vec{\ell}$, in polynomial time we can
compute a Turing machine $\mathsf{TM}_{D^{(2)}}\in\\{0,1\\}^{\mu\cdot\log T}$
such that

$\mathsf{Circuit}\left[T_{D^{(2)}},s_{D^{(2)}},T^{3}\cdot
2^{2s^{\prime}},T^{3}+|(n,d)|\right]\left(\mathsf{TM}_{D^{(2)}}\right)=D^{(2)},$

where $s_{D^{(2)}}=\mu\cdot s^{\prime}$.

  3. 3.

(Computing $\mathsf{Eval}$.) The final circuit $D^{(3)}$ takes $\langle\langle
C\rangle,n,d\rangle$ as input, and outputs $\mathsf{Eval}(\langle
C\rangle,n,d)$.

Complexity of $D^{(3)}$. $D^{(3)}$ can be implemented by a circuit of depth
$d_{D^{(3)}}=\mu\cdot d\cdot\log T$ and size $T_{D^{(3)}}=T^{\mu}$. Moreover,
from [CT21, Gol17] (note that $D^{(3)}$ does not depend on $\mathsf{TM}$),
given $\vec{\ell}$, in polynomial-time we can compute a Turing machine
$\mathsf{TM}_{D^{(3)}}\in\\{0,1\\}^{\mu\cdot\log T}$ such that

$\mathsf{Circuit}\left[T_{D^{(3)}},s_{D^{(3)}},T^{3}+|(n,d)|,n\right]\left(\mathsf{TM}_{D^{(3)}}\right)=D^{(3)},$

where $s_{D^{(3)}}=\mu\cdot s^{\prime}$.

Formally, we have

$D=D^{(3)}\circ D^{(2)}\circ D^{(1)}.$

Let $\beta\in\mathbb{N}$ be a sufficiently large constant such that $\beta\geq
100\mu$. The following claim summarizes the required properties of $D$ for us.

######  Claim 5.2.

The following properties about the circuit $D$ are true.

  1. 1.

The depth of $D$ is $d_{D}=\beta\cdot(\kappa^{2}\cdot\log^{2}T+d\cdot\log T)$
and the width of $D$ is $T^{\prime}_{D}=T^{\beta\kappa}$.

  2. 2.

The layered adjacency relation function
$\Phi^{\prime}\colon[d_{D}]\times\\{0,1\\}^{3\log(T^{\prime}_{D})}\rightarrow\\{0,1\\}$
of $D$ can be decided by a formula of depth $O(\log\log T)$ and size
$O(\log^{3}T)$. Moreover, there is an algorithm $\mathbb{A}_{\Phi^{\prime}}$
that given $\vec{\ell}$ and $\mathsf{TM}$ as input, outputs the formula above
in $O(\kappa\log T)$ space.

  3. 3.

There is a Turing machine $\mathsf{TM}_{D}\in\\{0,1\\}^{\beta\kappa\log T}$
such that

$\mathsf{Circuit}[T_{D},s_{D},n,n](\mathsf{TM}_{D})=D,$

where $T_{D}=T^{\prime}_{D}\cdot(d_{D}+1)$ and $s_{D}=\beta\kappa\log T$.
Moreover, given $\vec{\ell}$ and $\mathsf{TM}$ as input, the description of
$\mathsf{TM}_{D}$ can be computed in polynomial time.

###### Proof of 5.2.

By construction, the size of $D$ is bounded by $\mathrm{poly}(T)\cdot
2^{O(s^{\prime})}\leq T^{O(\kappa)}$ (recall that $s^{\prime}=O(s+\log(3\log
T))$ and $s=\kappa\log T$), and its depth is bounded by $O(s^{2}+d\cdot\log
T)$. The first bullet then follows directly from the fact that $\beta$ is
sufficiently large.

Recall that the $D^{(1)}$ part of $D$ has depth $d_{D^{(1)}}=2$. To see the
complexity of computing $\Phi^{\prime}(i,-,-,-)$ for $i>2$, we note that the
layers corresponding to $D^{(2)}$ and $D^{(3)}$ _do not_ depend on
$\mathsf{TM}$. Hence the complexity of computing their layered adjacent
relation function follows directly from [CT21, Claim 4.7.1].252525We note that
although [CT21, Gol17] only claims a $\mathrm{polylog}(T)$ bound on the
formula size, the formula is indeed very simple and its size and depth can be
easily bounded by $O(\log^{3}T)$ and $O(\log\log T)$, respectively; see
[Gol17, Page 8-9] for details. Also, the complexity of computing
$\Phi^{\prime}(i,-,-,-)$ for $i\in\\{1,2\\}$ follows directly from 2.2. To see
the moreover part, again, the case for $i>2$ follows from [CT21, Claim 4.7.1],
and the case for $i\in\\{1,2\\}$ follows from 2.2.262626Strictly speaking we
need to combine the formulas for two cases to obtain a single formula for
$\Phi^{\prime}$. The overhead of doing so is negligible so we omit this
discussion here.

Finally, to obtain the algorithm that computes $\mathsf{TM}_{D}$, we simply
apply the composition $\mathbb{A}_{\sf comp}$ (from 2.4) twice to compose the
circuits $D^{(1)},D^{(2)},D^{(3)}$ in order and add some dummy gates to the
circuit. The space bound and the description size bound can also be verified
easily. ∎

####  5.1.2 Arithmetization of $D$

The construction of the polynomials and their corresponding algorithms can
then be done in the same way as in [CT21]. We only state the necessary changes
to establish our theorem.

Note that $|\mathbb{F}|^{m}=p^{m}\leq\mathrm{poly}(h^{27m})\leq
T^{O(\beta\kappa)}\leq T^{O(\kappa)}$ ($\beta$ is a universal constant), from
our assumption that $p\leq h^{27}$ and our choice of $m$.

First, we need an arithmetization of each
$\Phi^{\prime}_{i}\triangleq\Phi^{\prime}(i,-,-,-)$.

######  Claim 5.3.

For $i\in[d_{D}]$ there exists a polynomial
$\hat{\Phi}_{i}\colon\mathbb{F}^{3m}\rightarrow\mathbb{F}$ that satisfies the
following:

  1. 1.

For every $(\vec{w},\vec{u},\vec{v})=z_{1},...,z_{3m}\in H^{3m}$ we have that
$\hat{\Phi}_{i}(\vec{w},\vec{u},\vec{v})=1$ if gate $\vec{w}$ in the $i^{th}$
layer of $D$ is fed by gates $\vec{u}$ and $\vec{v}$ in the $(i-1)^{th}$ layer
of $D$, and $\hat{\Phi}_{i}(\vec{w},\vec{u},\vec{v})=0$ otherwise.

  2. 2.

The degree of $\hat{\Phi}_{i}$ is at most $O(h\cdot\log^{3}T)$. Moreover,
there exists an algorithm that on input
$\vec{\ell},\mathsf{TM},i,\vec{w},\vec{u},\vec{v}$, computes
$\hat{\Phi}_{i}(\vec{w},\vec{u},\vec{v})$ in $\mathrm{poly}(h)$ time.

  3. 3.

For a universal constant $c_{1}>1$, there exists a circuit $C_{\hat{\Phi}}$ of
size $T_{\hat{\Phi}}\triangleq T^{c_{1}\kappa}$ and depth
$c_{1}\kappa\cdot\log T$ that on input $i\in[d_{D}]$ outputs
$\mathtt{tt}(\hat{\Phi}_{i})\in\mathbb{F}^{|\mathbb{F}|^{3m}}$ _(_ represented
as a Boolean string _)_. Moreover, there is a polynomial-time algorithm
$\mathbb{A}_{\hat{\Phi}}$ that takes $\vec{\ell}$ and
$\mathsf{TM}\in\\{0,1\\}^{\kappa\log T}$ as input, and outputs the description
of a Turing machine $\mathsf{TM}_{\hat{\Phi}}\in\\{0,1\\}^{c_{1}\kappa\log T}$
such that

$C_{\hat{\Phi}}=\mathsf{Circuit}\left[T_{\hat{\Phi}},c_{1}\cdot\kappa\log
T,\log(d_{D}+1),|\mathbb{F}|^{3m}\log|\mathbb{F}|\right](\mathsf{TM}_{\hat{\Phi}}).$

###### Proof Sketch of 5.3.

We first define $\hat{\Phi}_{i}$ and then establish each item separately.

##### Construction of $\hat{\Phi}_{i}$.

Let $F_{\Phi^{\prime}}$ be the $O(\log\log T)$-depth $O(\log^{3}T)$-size
formula computing $\Phi^{\prime}\colon[d_{D}]\times\\{0,1\\}^{3\cdot\log
T^{\prime}_{D}}\to\\{0,1\\}$ from 5.2. For every $i\in[d_{D}]$, let $F_{i}$ be
the restriction of $F_{\Phi^{\prime}}$ by fixing the first input to be $i$.
Then, we arithmetize $F_{i}$ by replacing every NAND gate in $F_{i}$ by an
arithmetic gate $\widetilde{\texttt{NAND}}:\mathbb{F}^{2}\to\mathbb{F}$
computing $\widetilde{\texttt{NAND}}(u,v)\triangleq 1-uv$. Denote the new
formula (which is now an _arithmetic_ formula) by $\hat{F}_{i}$.

For each $j$, let $\pi_{j}\colon H\to\\{0,1\\}$ be the mapping that maps $z\in
H$ to the $j$-th bit of the encoding of $z$. Note that since $H$ consists of
the smallest $h$ elements in $\mathbb{F}$, we know that
$\pi(z)=(\pi_{1}(z),\dotsc,\pi_{\log h}(z))$ is a bijection between $H$ and
$\\{0,1\\}^{\log h}$.272727More specifically, by our specific encoding of $H$
as strings from $\\{0,1\\}^{\log|\mathbb{F}|}$, $\pi(z)$ is simply the first
$\log h$ bits of the encoding of $z$, hence it can be computed by a
projection.

For each $j\in[\log h]$, let $\hat{\pi}_{j}\colon\mathbb{F}\to\mathbb{F}$ be
the unique degree-$(h-1)$ extension of $\pi_{j}$ to $\mathbb{F}$, that can be
computed via standard interpolation via logspace-uniform circuits of
$O(\log(h\cdot\log|\mathbb{F}|))=O(\log T)$ depth and $\mathrm{polylog}(T)$
size [HAB02, HV06] (see [CT21, Claim 4.7.2] for the details). We also let
$\hat{\pi}(z)=(\hat{\pi}_{1}(z),\dotsc,\hat{\pi}_{\log h}(z))$. Then, we set

$\hat{\Phi}_{i}(z_{1},\dots,z_{3m})\triangleq\hat{F}_{i}\left(\hat{\pi}(z_{1}),\hat{\pi}(z_{2}),\dots,\hat{\pi}(z_{3m})\right).$

We also use $F_{\hat{\Phi}_{i}}$ to denote the _arithmetic_ formula on the
right side above that computes the formula $\hat{\Phi}_{i}$.

From the construction above, the first two items of the claim can be proved
identically as [CT21, Claim 4.7.2]. It remains to establish the third item.

##### Construction of $C_{\hat{\Phi}}$.

We hardwire the description of $F_{\Phi^{\prime}}$ into $C_{\hat{\Phi}}$. The
circuit $C_{\hat{\Phi}}$ takes $i\in[d_{D}]$ as input, performs the above
computation to obtain a description of the arithmetic formula
$F_{\hat{\Phi}_{i}}$, and then outputs the truth table of $F_{\hat{\Phi}_{i}}$
by evaluating it on all vectors in $\mathbb{F}^{3m}$.

In more detail, computing the description of $F_{\hat{\Phi}_{i}}$ from the
description of $F_{\Phi^{\prime}}$ and $i$ can be done in $O(\log T)$ depth
and $\mathrm{polylog}(T)$ size. $C_{\hat{\Phi}}$ then evaluates
$F_{\hat{\Phi}_{i}}$ on all vectors from $\mathbb{F}^{m}$, which can be done
in $\mathrm{poly}(|\mathbb{F}|^{m})$ size and $O(\log(|\mathbb{F}|^{m}))$
depth. The third bullet (except for the moreover part) then follows by setting
$c_{1}$ to be sufficiently large and recalling that $|\mathbb{F}|^{m}\leq
T^{O(\beta\kappa)}$.

##### Establishing the uniformity.

Finally, we establish the moreover part of the third bullet. Let
$\mu_{\hat{\Phi}}\in\mathbb{N}$ be a sufficiently large universal constant
that depends on the space complexity of the algorithm
$\mathbb{A}_{\Phi^{\prime}}$ from 5.2.

Our algorithm $\mathbb{A}_{\hat{\Phi}}$ works as follows:

  1. 1.

We first construct a Turing machine $\mathsf{TM}_{[1]}$ with $\vec{\ell}$ and
$\mathsf{TM}$ hardwired. $\mathsf{TM}_{[1]}$ corresponds to a circuit
$C_{[1]}$ that takes $i\in[d_{D}]$ as input and outputs $i$ together with the
description of $F_{\Phi^{\prime}}$.282828Precisely, $\mathsf{TM}_{[1]}$
simulates $\mathbb{A}_{\Phi^{\prime}}$ on input $\vec{\ell}$ and $\mathsf{TM}$
to construct a projection that maps $i$ to $(i,F_{\Phi^{\prime}})$. $C_{[1]}$
has depth $d_{[1]}=O(1)$ and size $T_{[1]}=\mathrm{polylog}(T)$. Let
$s_{[1]}=\mu_{\hat{\Phi}}\cdot\kappa\log T$, we have

$C_{[1]}=\mathsf{Circuit}\left[T_{[1]},s_{[1]},\log d_{D},\log
d_{D}+|F_{\Phi^{\prime}}|\right]\left(\mathsf{TM}_{[1]}\right)$

and $\mathsf{TM}_{[1]}$ has description size at most
$|\mathsf{TM}|+\mu_{\hat{\Phi}}\cdot\log T=(\kappa+\mu_{\hat{\Phi}})\cdot\log
T$.

Here, we crucially use the fact that the algorithm
$\mathbb{A}_{\Phi^{\prime}}$ from 5.2 runs in $O(\kappa\log T)$ space (and
$\mu_{\hat{\Phi}}$ is sufficiently large).

  2. 2.

Then we construct a Turing machine $\mathsf{TM}_{[2]}$ that corresponds to a
circuit $C_{[2]}$ that takes $i\in[d_{D}]$ together with the description of
$F_{\Phi^{\prime}}$ as input and outputs $\mathtt{tt}(\hat{\Phi}_{i})$. By the
discussion above, from $\vec{\ell}$ we can compute a Turing machine
$\mathsf{TM}_{[2]}\in\\{0,1\\}^{\mu_{\hat{\Phi}}\kappa\log T}$ such that for
$T_{[2]}=\mathrm{poly}(|\mathbb{F}|^{m})\leq T^{\mu_{\hat{\Phi}}\kappa}$,
$d_{[2]}=O(\log(|\mathbb{F}|^{m}))\leq\mu_{\hat{\Phi}}\kappa\cdot\log T$,
$s_{[2]}=\mu_{\hat{\Phi}}\kappa\log T$, we have

$C_{[2]}=\mathsf{Circuit}\left[T_{[2]},s_{[2]},\log
d_{D}+|F_{\Phi^{\prime}}|,|\mathbb{F}|^{3m}\right]\left(\mathsf{TM}_{[2]}\right)\;\text{,}$

and $C_{[2]}$ has depth $d_{[2]}$.

  3. 3.

Finally, $\mathbb{A}_{\hat{\Phi}}$ composes $C_{[1]}$ and $C_{[2]}$ by
applying 2.4 and outputs the obtained Turing machine as
$\mathsf{TM}_{\hat{\Phi}}$. Setting $c_{1}$ sufficiently large completes the
proof.∎

Then we define the following polynomials, according to [CT21, Definition 4.6].

##### Input polynomial.

Let $\alpha_{0}\colon H^{m}\rightarrow\\{0,1\\}$ represent the string
$1^{n}0^{h^{m}-n}$, and let
$\hat{\alpha}_{0}\colon\mathbb{F}^{m}\rightarrow\mathbb{F}$ be the
“arithmetization” of $\alpha_{0}$, defined by

$\hat{\alpha}_{0}(\vec{w})=\sum_{\vec{z}\in
H^{m^{\prime}}\times\left\\{0\right\\}^{m-m^{\prime}}}\delta_{\vec{z}}(\vec{w})\cdot\alpha_{0}(\vec{z}).$

Here, $m^{\prime}\leq m$ is the minimal integer such that $h^{m^{\prime}}\geq
n$, and $\delta_{\vec{z}}$ is Kronecker’s delta function (i.e.,
$\delta_{\vec{z}}(\vec{w})=\prod_{j\in[m]}\prod_{a\in
H\setminus\left\\{z_{j}\right\\}}\frac{w_{j}-a}{z_{j}-a}$).

##### Layer polynomials.

For each $i\in[d_{D}]$, let $\alpha_{i}\colon H^{m}\rightarrow\\{0,1\\}$
represent the values of the gates at the $i^{th}$ layer of $D$ in the
computation of $D(1^{n})$ (with zeroes in locations that do not index valid
gates). Recall that we consider circuits consisting of $\mathsf{NAND}$ gates,
where for $a,b\in\\{0,1\\}$ we have $\mathsf{NAND}(a,b)=1-a\cdot b$. We define
$\hat{\alpha}_{i}\colon\mathbb{F}^{m}\rightarrow\mathbb{F}$ as

$\hat{\alpha}_{i}(\vec{w})=\sum_{\vec{u},\vec{v}\in
H^{m}}\hat{\Phi}_{i}(\vec{w},\vec{u},\vec{v})\cdot\left(1-\hat{\alpha}_{i-1}(\vec{u})\cdot\hat{\alpha}_{i-1}(\vec{v})\right).$
(5)

Note that $\hat{\alpha}_{i}$ is the “arithmetization” of $\alpha_{i}$ in the
sense that for every $\vec{w}\in H^{m}$,
$\alpha_{i}(\vec{w})=\hat{\alpha}_{i}(\vec{w})$.

##### Sumcheck polynomials.

For each $i\in[d_{D}]$, let
$\hat{\alpha}_{i,0}\colon\mathbb{F}^{3m}\rightarrow\mathbb{F}$ be the
polynomial

$\hat{\alpha}_{i,0}(\vec{w},\sigma_{1},...,\sigma_{2m})=\hat{\Phi}_{i}(\vec{w},\sigma_{1,...,m},\sigma_{m+1,...,2m})\cdot\left(1-\hat{\alpha}_{i-1}(\sigma_{1,...,m})\cdot\hat{\alpha}_{i-1}(\sigma_{m+1,...,2m})\right).$
(6)

For every $j\in[2m]$, let
$\hat{\alpha}_{i,j}\colon\mathbb{F}^{3m-j}\rightarrow\mathbb{F}$ be the
polynomial

$\displaystyle\hat{\alpha}_{i,j}(\vec{w},\sigma_{1},...,\sigma_{2m-j})=$
$\displaystyle\sum_{\sigma_{2m-j+1},...,\sigma_{2m}\in
H}\hat{\Phi}_{i}(\vec{w},\sigma_{1,...,m},\sigma_{m+1,...,2m})\cdot\left(1-\hat{\alpha}_{i-1}(\sigma_{1,...,m})\cdot\hat{\alpha}_{i-1}(\sigma_{m+1,...,2m})\right),$
(7)

where $\sigma_{k,...,k+r}=\sigma_{k},\sigma_{k+1},...,\sigma_{k+r}$. It is
easy to check that $\hat{\alpha}_{i,2m}=\hat{\alpha}_{i}$.

We are now ready to define the sequence
$(P_{i})_{i\in[d^{\prime}]}=\left(P_{i}^{\vec{\ell},\mathsf{TM}}\right)_{i\in[d^{\prime}]}$.
We set $d^{\prime}\triangleq(2m+1)\cdot d_{D}+1$ and

$(P_{i})_{i\in[d^{\prime}]}=(\hat{\alpha}_{0},\hat{\alpha}_{1,0},\dotsc,\hat{\alpha}_{1,2m},\hat{\alpha}_{2,0},\dotsc,\hat{\alpha}_{2,2m},\dotsc,\hat{\alpha}_{d_{D},0},\dotsc,\hat{\alpha}_{d_{D},2m}).$

For those $\hat{\alpha}_{i,j}$ (and $\hat{\alpha}_{0}$) that take less than
$3m$ variables, we add some dummy variables at the end to make all polynomials
taking exactly $3m$ variables.

From the definitions of $m$ and $d_{D}$, we have $m\leq
3\cdot\beta\kappa\cdot\log T+1$ and
$d_{D}=\beta\cdot(\kappa^{2}\cdot\log^{2}T+d\cdot\log T)$. Hence, we have
$d^{\prime}=(2m+1)\cdot d_{D}+1\leq
c\kappa\cdot\log^{2}T\cdot(d+\kappa^{2}\log T)$ as desired.292929We can add
identical polynomials at the end to make $d^{\prime}$ exactly
$c\kappa\cdot\log^{2}T\cdot(d+\kappa^{2}\log T)$ as in the theorem statement.

Below we verify the desired properties of the sequence
$(P_{i})_{i\in[d^{\prime}]}$.

##### Arithmetic setting, faithful representation, and downward self-
reducibility.

First, the degree bounds of all these polynomials follow directly from their
definitions and from the degree bound on $\hat{\Phi}_{i}$ (from 5.3). The
faithful representation property also follows directly from the definition of
$\alpha_{d_{D}}$ and $\hat{\alpha}_{d_{D},2m}=\hat{\alpha}_{d_{D}}$. Finally,
the downward self-reducibility of the polynomials follows from the complexity
of computing $\hat{\Phi}_{i}$ (from 5.3) and the definitions of these
polynomials, similarly to the proof of [CT21, Proposition 4.7].

####  5.1.3 Complexity of the Polynomials

Now we verify the complexity of computing these polynomials. The argument
below is straightforward but tedious. We first give a high-level overview.

##### High-level overview of the construction.

To construct the circuit $C_{\sf poly}$ that maps $i^{\prime}\in[d^{\prime}]$
to $\mathtt{tt}(P_{i})$, we will construct three subcircuits $C_{\alpha}$,
$C_{\mathtt{tt}\text{-}\lower 0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$, and
$C_{\mathsf{arith}}$ such that:

  1. 1.

$C_{\alpha}$ maps $i^{\prime}\in[d^{\prime}]$ to
$(\mathtt{tt}(\alpha_{i-1}),i,j)$. Here, if $i^{\prime}\geq 2$, then
$i\in\\{1,\dots,d_{D}\\}$ and $j\in\\{0,1,\dots,2m\\}$ satisfies that
$P_{i^{\prime}}=\hat{\alpha}_{i,j}$ and
$\mathtt{tt}(\alpha_{i-1})\in\\{0,1\\}^{h^{m}}$ denotes the values of the
gates at the $i$-th layer of $D$. If $i^{\prime}=1$, then we consider $i=j=0$
and $C_{\alpha}$ outputs $(\mathtt{tt}(\alpha_{0}),0,0)$.

  2. 2.

$C_{\mathtt{tt}\text{-}\lower 0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$ maps
$(\mathtt{tt}(\alpha_{i-1}),i,j)$ to
$(\mathtt{tt}(\alpha_{i-1}),i,j,\mathtt{tt}(\hat{\Phi}_{i}))$.

  3. 3.

$C_{\mathsf{arith}}$ maps
$(\mathtt{tt}(\alpha_{i-1}),i,j,\mathtt{tt}(\hat{\Phi}_{i}))$ to
$\mathtt{tt}(\hat{\alpha}_{i,j})\in\mathbb{F}^{|\mathbb{F}|^{3m}}$.

$C_{\sf poly}$ is then simply $C_{\mathsf{arith}}\circ
C_{\mathtt{tt}\text{-}\lower 0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}\circ
C_{\alpha}$. To compute the Turing machine $\mathsf{TM}_{\sf poly}$ that
corresponds to $C_{\sf poly}$, we construct the Turing machines
$\mathsf{TM}_{\alpha}$, $\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$, and $\mathsf{TM}_{\mathsf{arith}}$
corresponding to the three circuit above, and compose them using 2.4.

##### Construction of $C_{\alpha}$ and $\mathsf{TM}_{\alpha}$.

First, we construct a circuit $C_{\alpha}$ that takes as input
$i^{\prime}\in[d^{\prime}]$ and outputs $(\mathtt{tt}(\alpha_{i-1}),i,j)$. To
construct $C_{\alpha}$, we first compute $i$ and $j$ from $i^{\prime}$ using
basic arithmetic, and then truncate $D$ up to its $i$-th layer. It is easy to
see that given the Turing machine $\mathsf{TM}_{D}$ that specifies the circuit
$D$, in polynomial-time we can construct a Turing machine
$\mathsf{TM}_{\alpha}\in\\{0,1\\}^{|\mathsf{TM}_{D}|+\mu}$ such that (in what
follows, we write $|\langle i,j\rangle|=\log(d_{D}+1)+\log(2m+1)$ for
convenience):

$\mathsf{Circuit}[T_{\alpha},s_{\alpha},\log(d^{\prime}),h^{m}+|\langle
i,j\rangle|](\mathsf{TM}_{\alpha})=C_{\alpha},$

where $T_{\alpha}=\mu\cdot T_{D}$, $s_{\alpha}=2s_{D}$. Moreover, $C_{\alpha}$
has depth at most $d_{\alpha}=2\cdot d_{D}$.

##### Construction of $C_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$ and
$\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$.

Let $c_{1}$ be the universal constant from 5.3. Next we construct a circuit
$C_{\mathtt{tt}\text{-}\lower 0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$ that
on input $(\mathtt{tt}(\alpha_{i-1}),i,j)$, outputs
$(\mathtt{tt}(\alpha_{i-1}),i,j,\mathtt{tt}(\hat{\Phi}_{i}))$. It is
straightforward to obtain this circuit from the circuit $C_{\hat{\Phi}}$
constructed in 5.3. In other words, given $\vec{\ell}$ and
$\mathsf{TM}_{\hat{\Phi}}\in\\{0,1\\}^{c_{1}\kappa\log T}$ as input (where
$\mathsf{TM}_{\hat{\Phi}}$ is the Turing machine that generates
$C_{\hat{\Phi}}$ as defined in 5.3), we can compute a Turing machine
$\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}\in\\{0,1\\}^{2\cdot c_{1}\kappa\log
T}$ such that

$\mathsf{Circuit}[T_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}},s_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}},h^{m}+|\langle
i,j\rangle|,h^{m}+|\langle
i,j\rangle|+|\mathbb{F}|^{3m}\log|\mathbb{F}|](\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}})=C_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}},$

where $T_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}=T^{2c_{1}\kappa}$,
$s_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}=2c_{1}\kappa\log T$. Moreover,
$C_{\mathtt{tt}\text{-}\lower 0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$ has
depth $d_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}=2c_{1}\kappa\log T$.

##### Construction of $C_{\mathsf{arith}}$ and $\mathsf{TM}_{\mathsf{arith}}$.

We construct a circuit $C_{\mathsf{arith}}$ that maps
$(\mathtt{tt}(\alpha_{i-1}),i,j,\mathtt{tt}(\hat{\Phi}_{i}))$ to
$\mathtt{tt}(\hat{\alpha}_{i,j})\in\mathbb{F}^{|\mathbb{F}|^{3m}}$. (Recall
that throughout this proof we view $\hat{\alpha}_{i,j}$ as a $3m$-variable
polynomial by adding dummy variables at the end.) Suppose that $i\geq 1$ (the
base case $i=j=0$ can be handled similarly). If $j=0$, $C_{\mathsf{arith}}$
computes $\mathtt{tt}(\hat{\alpha}_{i,0})$ using Equation 6, otherwise ($j\geq
1$) $C_{\mathsf{arith}}$ computes $\mathtt{tt}(\hat{\alpha}_{i,j})$ using
Equation 7. (Note that both Equation 6 and Equation 7 only depend on the
values of $\hat{\alpha}_{i-1}$ over $H^{m}$, which is exactly
$\mathtt{tt}(\alpha_{i-1})$ due to our arithmetization.) Since arithmetic
operations over $\mathbb{F}$ (including iterated addition, multiplication, and
inverse) are in logspace-uniform $\NC^{1}$ [HAB02, HV06],303030It is in fact
in logtime-uniform $\TC^{0}$, but here we only need it to be in logspace-
uniform $\NC^{1}$. it follows that $C_{\mathsf{arith}}$ is of $T_{\sf
arith}\triangleq\mathrm{poly}(|\mathbb{F}|^{m})$ size and $d_{\sf
arith}\triangleq O(m\log|\mathbb{F}|)$ depth. Moreover, $C_{\mathsf{arith}}$
does not depend on $\mathsf{TM}$, and we can compute a Turing machine
$\mathsf{TM}^{\mathsf{arith}}$ from $\vec{\ell}$ in time $\mathrm{polylog}(T)$
such that

$\mathsf{Circuit}[T_{\sf arith},s_{\mathsf{arith}},h^{m}+|\langle
i,j\rangle|+|\mathbb{F}|^{3m}\log|\mathbb{F}|,|\mathbb{F}|^{3m}\log|\mathbb{F}|](\mathsf{TM}^{\mathsf{arith}})=C_{\mathsf{arith}},$

where $s_{\mathsf{arith}}=\mu\cdot\beta\kappa\log T$.

Composing $\mathsf{TM}_{\alpha}$, $\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}$, and $\mathsf{TM}_{\mathsf{arith}}$
by applying 2.4 twice gives the desired Turing machine $\mathsf{TM}_{\sf
poly}$ that computes the desired circuit $C_{\sf poly}$.

##### Complexity of $C_{\sf poly}$ and $\mathsf{TM}_{\sf poly}$.

Finally, we verify that $\mathsf{TM}_{\sf poly}$ and $C_{\sf poly}$ satisfy
our requirements. First, from the discussions above, we can bound the size of
$C_{\sf poly}$ by $T_{\alpha}+T_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}+T_{\mathsf{arith}}\leq
T_{\sf\mathrm{poly}}=2^{c\cdot\kappa\log T}$ by picking a sufficiently large
$c$. Note that $m\log|\mathbb{F}|=\log(p^{m})\leq O(\kappa\log T)$. The depth
of $C_{\sf poly}$ can be bounded by $d_{\sf
poly}=d_{\alpha}+d_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}+d_{\mathsf{arith}}\leq
c\cdot(\kappa^{2}\cdot\log^{2}T+d\cdot\log T)$ as desired.

From 2.4, we have that

$|\mathsf{TM}_{\sf poly}|\leq
100\cdot\left(|\mathsf{TM}_{\alpha}|+|\mathsf{TM}_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}|+|\mathsf{TM}_{\mathsf{arith}}|+\log(|\mathbb{F}|^{3m})\right)\leq
c\cdot\kappa\log T=\log T_{\sf poly}$

by setting $c$ sufficiently large. The space complexity of $\mathsf{TM}_{\sf
poly}$ can be bounded by

$100\cdot\left(s_{\alpha}+s_{\mathtt{tt}\text{-}\lower
0.60275pt\hbox{\scriptsize$\hat{\Phi}$}}+s_{\mathsf{arith}}\right)\leq
c\cdot\kappa\log T=\log T_{\sf poly}$

as well. This completes the proof. ∎

###  5.2 Improved Chen–Tell Generator: Proof of Theorem 3.1

Now we are ready to prove Theorem 3.1 by plugging every polynomial from
Theorem 5.1 into our modified Shaltiel–Umans generator (Section 4).

###### Proof of Theorem 3.1.

We first observe that we can assume $\rho=1$ without loss of generality. To
see how the general case follows from the case that $\rho=1$, letting
$M^{\prime}=M^{\rho}$, we can simply define $\mathsf{H}^{\sf
ct}_{n,T,d,M,\kappa,\rho}$ as the set of strings obtained by truncating every
string from $\mathsf{H}^{\sf ct}_{n,T,d,M^{\prime},\kappa,1}$ to their first
$M$ bits. The reconstruction algorithm $\mathsf{R}^{\sf
ct}_{n,T,d,M,\kappa,\rho}$ can then be obtained by slightly modifying
$\mathsf{R}^{\sf ct}_{n,T,d,M^{\prime},\kappa,1}$.

Let

$\vec{\ell}_{\sf ct}=(n,T,d,M,\kappa,1)$

be the input parameters from the theorem statement and $c$ be a sufficiently
large universal constant. From the assumption, we have $n\leq T,d\leq T$, and
$c\cdot\log T\leq M\leq T^{1/c}$. Let

$C_{\mathsf{TM}}=\mathsf{Circuit}[T,\kappa\cdot\log T,n,n](\mathsf{TM}).$

##### The layered-polynomial representation.

Let $c_{0},c_{0}^{\prime},\beta$ be the universal constants from Theorem 5.1.
Let $h$ be the _smallest_ nice power of $2$ such that $h\geq M$, $p\triangleq
h^{27}$, $m$ be the smallest power of $3$ such that $h^{m}\geq
T^{\beta\kappa}$, and $\mathbb{F}=\mathbb{F}_{p}$. Note that $p$ is also a
nice power of $2$ and $h\leq M^{3}$.

We will invoke Theorem 5.1 with input parameters

$\vec{\ell}_{\sf poly}=(\kappa,T,d,n,h,p).$

Note that from their definitions and our assumption $M\geq c\log T$, we have
$\log T\leq h<p\leq h^{27}\leq M^{81}\leq T$ (assuming $c\geq 81$ is large
enough), meaning that the requirements on the input parameters of Theorem 5.1
are satisfied.

We first apply Theorem 5.1 with input parameters $\vec{\ell}_{\sf poly}$ and
Turing machine $\mathsf{TM}$ to obtain
$d^{\prime}=c_{0}\kappa\cdot\log^{2}T\cdot(d+\kappa^{2}\log T)$ polynomials
$(P_{i})_{i\in[d^{\prime}]}=\left(P_{i}^{\vec{\ell},\mathsf{TM}}\right)_{i\in[d^{\prime}]}$.

##### Hitting set $\mathsf{H}^{\sf ct}$.

Let $\mathsf{H}^{\sf layer}$ and $\mathsf{R}^{\sf layer}$ denote the
$\mathsf{H}$ and $\mathsf{R}$ algorithms from Section 4,
respectively.313131The superscript layer highlights the fact that they are
applied to each layer of the polynomial representation of the circuit. Let
$\Delta=c_{0}h\log^{3}(T)$,

$\vec{\ell}_{\sf layer}=(p,3m,M,\Delta)$

be the input parameters when applying Section 4. We can verify that
$p>\Delta^{2}(3m)^{7}M^{9}$, i.e., the requirement on the input parameters of
Section 4 is satisfied.

We then define $\mathsf{H}^{\sf ct}_{\vec{\ell}_{\sf ct}}(\mathsf{TM})$ as the
union of $\mathsf{H}^{\sf layer}_{\vec{\ell}_{\sf layer}}(P_{i})$ for every
$i\in[d^{\prime}]$. Next we analyze the complexity of computing
$\mathsf{H}^{\sf ct}_{\vec{\ell}_{\sf ct}}(\mathsf{TM})$. First, from Theorem
5.1, letting $T_{\sf poly}=T^{c_{0}\cdot\kappa}$ and $d_{\sf
poly}=c_{0}\cdot(d\log T+\kappa^{2}\log^{2}T)$, there is a polynomial-time
algorithm $\mathbb{A}^{\sf poly}_{\vec{\ell}}$ that takes
$\mathsf{TM}\in\\{0,1\\}^{\kappa\log T}$ as input, and outputs a description
of Turing machine $\mathsf{TM}_{\sf poly}\in\\{0,1\\}^{\log T_{\sf poly}}$
such that for

$C_{\sf poly}=\mathsf{Circuit}\left[T_{\sf poly},\log T_{\sf poly},\log
d^{\prime},|\mathbb{F}|^{3m}\cdot\log|\mathbb{F}|\right](\mathsf{TM}_{\sf
poly})$

it holds that (1) for every $i\in[d^{\prime}]$ $C_{\sf
poly}(i)=\mathtt{tt}(P_{i})$ and (2) $C_{\sf poly}$ has depth $d_{\sf poly}$.

Second, from Section 4, there is a logspace-uniform circuit family with input
parameters $\vec{\ell}_{\sf layer}$, size $\mathrm{poly}(p^{m})$, and depth
$\mathrm{poly}(\log p,m,M)$ such that for every $i\in[d^{\prime}]$, it outputs
$\mathsf{H}^{\sf layer}_{\vec{\ell}_{\sf layer}}(P_{i})$ when taking
$\mathtt{tt}(P_{i})$ as input. Note that $\mathrm{poly}(p^{m})\leq
T^{O(\beta\kappa)}$ and $\mathrm{poly}(\log p,m,M)\leq\mathrm{poly}(M)$.
Applying 2.4 to compose the machines above and enumerating over all
$i\in[d^{\prime}]$,323232Enumerating all $i\in[d^{\prime}]$ only adds a
$O(\log d^{\prime})$ additive overhead in depth and a $O(d^{\prime})$
multiplicative blowup in size, which are negligible. we obtain the desired
circuit $C_{\sf H}$ (note that $c$ is sufficiently large).

##### Reconstruction $\mathsf{R}^{\sf ct}$.

For every $i\in\\{2,\dotsc,d^{\prime}\\}$, the reconstruction algorithm
$\mathsf{R}^{\sf ct}$ attempts to construct a
$\mathrm{poly}(p,m,\log(Md^{\prime}))$-size $D$-oracle circuit $E_{i}$ that
computes $P_{i}$. A formal description of $\mathsf{R}^{\sf ct}$ is as follows:

  * •

We start with the circuit
$E_{1}(\vec{x})=\mathsf{Base}(\vec{\ell},\mathsf{TM},\vec{x})$ that computes
the polynomial $P_{1}$.

  * •

For every $i\in\\{2,\dotsc,d^{\prime}\\}$:

    1. 1.

We first construct a procedure $\widetilde{P}_{i}$ computing $P_{i}$ using the
$D$-oracle circuit $E_{i-1}^{D}$ for $P_{i-1}$ and the downward self-
reducibility for $P_{i}$. In particular, on input $\vec{x}\in\mathbb{F}^{3m}$,
let

$\widetilde{P}_{i}(\vec{x})\triangleq\mathsf{DSR}^{E_{i-1}^{D}}(\vec{\ell},\mathsf{TM},i,\vec{x}).$

    2. 2.

Run $\left(\mathsf{R}^{\sf
layer}\right)^{D,\widetilde{P}_{i}}_{\vec{\ell}_{\sf layer}}$ which outputs a
$D$-oracle circuit $\widetilde{E}_{i}^{D}$ in $\mathrm{poly}(p,m,M)$ time.

    3. 3.

Let $t\triangleq c_{1}\cdot m\cdot\log p$ for a sufficiently large constant
$c_{1}>1$. Take $t$ i.i.d. samples $\vec{x}_{1},\dotsc,\vec{x}_{t}$ from
$\mathbb{F}^{3m}$. Check that for every $j\in[t]$,
$\widetilde{E}^{D}_{i}(\vec{x}_{j})=\widetilde{P}_{i}(\vec{x}_{j})$. If any
condition does not hold, the algorithm outputs $\bot$ and aborts immediately.

    4. 4.

Let $E_{i}$ be a $D$-oracle circuit constructed as follows:

      1. (a)

Draw $t=\Theta(m\log p)$ i.i.d. samples of random strings $r_{1},\dotsc,r_{t}$
used by $\mathsf{PCorr}$. (Recall that $\mathsf{PCorr}$ is the self-corrector
for low-degree polynomials in Theorem 4.7.)

      2. (b)

Set
$E_{i}(\vec{x})=\mathsf{MAJ}_{k\in[t]}~{}\mathsf{PCorr}^{\widetilde{E}_{i}}(p,3m,\Delta,\vec{x};r_{k})$
for all $\vec{x}\in\mathbb{F}^{3m}$.

  * •

For every $j\in[n]$, output $E_{d^{\prime}}^{D}(\mathsf{id}(j),0^{2m})$.

For ease of notation, for every $i^{\prime}\in\\{2,\dotsc,d^{\prime}\\}$, we
use $\tau_{i^{\prime}}$ to denote the randomness used when running the
algorithm above with $i=i^{\prime}$, and we use $\tau_{\leq i}$ to denote
$\tau_{1},\dotsc,\tau_{i}$. Also, if $E_{i}$ is not constructed by the
algorithm (meaning that the algorithm aborts before constructing $E_{i}$), we
set $E_{i}=\bot$.

From Theorem 4.7, Section 4, and Theorem 5.1, the running time of the
algorithm above can be bounded by

$\mathrm{poly}(p,m,h,\log(Md^{\prime}))\cdot(d^{\prime}+n)\leq\mathrm{poly}(M)\cdot(d^{\prime}+n)\leq\mathrm{poly}(M)\cdot(d+n).$

The last inequality follows from the fact that $M\geq\log T$ and hence
$d^{\prime}=c_{0}\kappa\cdot\log^{2}T\cdot(d+\kappa^{2}\log
T)\leq\mathrm{poly}(M)\cdot d$. Now we establish the soundness and
completeness of the reconstruction. We show the following claim.

######  Claim 5.4.

Fix $D\colon\\{0,1\\}^{M}\rightarrow\\{0,1\\}$. For every
$i\in\\{2,\dotsc,d^{\prime}\\}$, for every fixed $\tau_{\leq i-1}$, if
$E_{i-1}^{D}$ computes $P_{i-1}$ or $i=2$,333333Note that $\tau_{\leq i-1}$
determines $E_{i-1}$. then with probability at least $1-1/p^{m}$ over
$\tau_{i}$ the following holds:

  * •

(Soundness.) If $E_{i}\neq\bot$, then $E_{i}^{D}$ computes $P_{i}$.

  * •

(Completeness.) If $D$ $(1/M)$-avoids $\mathsf{H}^{\sf layer}_{\vec{\ell}_{\sf
layer}}(P_{i})$, then $E_{i}^{D}$ computes $P_{i}$.

Before establishing the claim, we show it implies the completeness and
soundness of the reconstruction. To see the soundness, note that by induction
over all $i\in\\{2,\dotsc,d^{\prime}\\}$, with probability at least
$1-d^{\prime}/p^{m}>9/10$, it holds that if $E_{d^{\prime}}\neq\bot$, then
$E_{d^{\prime}}$ computes $P_{d^{\prime}}$, meaning the reconstruction outputs
the correct output $C_{\mathsf{TM}}(1^{n})$. To see the completeness, note
that an oracle $D\colon\\{0,1\\}^{M}\rightarrow\\{0,1\\}$ that $(1/M)$-avoids
$\mathsf{H}^{\sf ct}_{\vec{\ell}}(\mathsf{TM})$ also $(1/M)$-avoids
$\mathsf{H}^{\sf layer}_{\vec{\ell}_{\sf layer}}(P_{i})$ for every
$i\in[d^{\prime}]$. Hence, by induction over $i\in\\{2,\dotsc,d^{\prime}\\}$,
with probability at least $1-d^{\prime}/p^{m}>9/10$, it holds that $E_{i}$
computes $P_{i}$ for every $i\in\\{2,\dotsc,d^{\prime}\\}$. Thus the
reconstruction will output $C_{\mathsf{TM}}(1^{n})$. The success probability
$9/10$ can be amplified to $1-2^{-M}$ by running the reconstruction algorithm
$O(M)$ times independently and outputting the answer that occurs most
frequently.

Finally, we prove the claim.

###### Proof of 5.4.

We first establish the soundness. From the assumption that $E_{i-1}^{D}$
computes $P_{i-1}$ or $i=2$ and the downward self-reducibility property of
Theorem 5.1, it follows that $\widetilde{P}_{i}$ computes $P_{i}$. Therefore,
$E_{i}\neq\bot$ means that $\widetilde{E}_{i}$ has passed the test in Step 3,
meaning that with probability at least $1-p^{-4m}$ over the randomness in Step
3, it holds that $\widetilde{E}_{i}$ agrees $P_{i}$ on at least $3/4$ fraction
of inputs from $\mathbb{F}^{3m}$. This then means that with probability at
least $1-p^{-3m}$ over the randomness in Step 4(a), we have $E_{i}^{D}$
computes $P_{i}$.

The completeness follows immediately from Section 4. (Here
$\widetilde{E}_{i}^{D}$ already computes $P_{i}$ with probability at least
$1-1/p^{m}$.) ∎

This completes the proof of Theorem 3.1. ∎

## Acknowledgments

Lijie Chen is supported by a Miller Research Fellowship. Igor C. Oliveira
received support from the EPSRC New Horizons Grant EP/V048201/1, the Royal
Society University Research Fellowship URF$\setminus$R1$\setminus$191059, and
the Centre for Discrete Mathematics and its Applications (DIMAP) at the
University of Warwick. Hanlin Ren received support from DIMACS through grant
number CCF-1836666 from the National Science Foundation. This work was done in
part while the authors were visiting the Simons Institute for the Theory of
Computing.

## References

  * [AB09] Sanjeev Arora and Boaz Barak.  Computational Complexity: A Modern Approach.  Cambridge University Press, 2009.
  * [AKS04] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.  PRIMES is in $\P$.  Annals of Mathematics, 160(2):781–793, 2004.  doi:10.4007/annals.2004.160.781.
  * [BB18] Ben Berger and Zvika Brakerski.  Zero-knowledge protocols for search problems.  In International Conference on Security and Cryptography for Networks _(SCN)_ , pages 292–309, 2018.  doi:10.1007/978-3-319-98113-0\\_16.
  * [BHP01] R. C. Baker, G. Harman, and J. Pintz.  The difference between consecutive primes. II.  Proc. London Math. Soc. (3), 83(3):532–562, 2001.  doi:10.1112/plms/83.3.532.
  * [BKKS23] Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Shay Sapir.  Lower bounds for pseudo-deterministic counting in a stream.  CoRR, abs/2303.16287, 2023.  doi:10.48550/arXiv.2303.16287.
  * [BM84] Manuel Blum and Silvio Micali.  How to generate cryptographically strong sequences of pseudo-random bits.  SIAM J. Comput., 13(4):850–864, 1984.  doi:10.1137/0213053.
  * [CDM23] Arkadev Chattopadhyay, Yogesh Dahiya, and Meena Mahajan.  Query complexity of search problems.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 2023.  URL: https://eccc.weizmann.ac.il/report/2023/039/.
  * [CPW23] Suvradip Chakraborty, Manoj Prabhakaran, and Daniel Wichs.  A map of witness maps: New definitions and connections.  Cryptology ePrint Archive, Paper 2023/343, 2023.  URL: https://eprint.iacr.org/2023/343.
  * [Cra36] Harald Cramér.  On the order of magnitude of the difference between consecutive prime numbers.  Acta Arithmetica, 2:23–46, 1936.
  * [CRT22] Lijie Chen, Ron D. Rothblum, and Roei Tell.  Unstructured hardness to average-case randomness.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 429–437. IEEE, 2022.  doi:10.1109/FOCS54457.2022.00048.
  * [CT21] Lijie Chen and Roei Tell.  Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise.  In IEEE Symposium on Foundations of Computer Science _(FOCS)_ , pages 125–136, 2021.  doi:10.1109/FOCS52979.2021.00021.
  * [DPV18] Peter Dixon, Aduri Pavan, and N. V. Vinodchandran.  On pseudodeterministic approximation algorithms.  In Symposium on Mathematical Foundations of Computer Science _(MFCS)_ , pages 61:1–61:11, 2018.  doi:10.4230/LIPIcs.MFCS.2018.61.
  * [DPV21] Peter Dixon, Aduri Pavan, and N. V. Vinodchandran.  Complete problems for multi-pseudodeterministic computations.  In Innovations in Theoretical Computer Science _(ITCS)_ , 2021\.  doi:10.4230/LIPIcs.ITCS.2021.66.
  * [DPWV22] Peter Dixon, Aduri Pavan, Jason Vander Woude, and N. V. Vinodchandran.  Pseudodeterminism: promises and lowerbounds.  In ACM Symposium on Theory of Computing _(STOC)_ , pages 1552–1565, 2022.  doi:10.1145/3519935.3520043.
  * [GG11] Eran Gat and Shafi Goldwasser.  Probabilistic search algorithms with unique answers and their cryptographic applications.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 18:136, 2011.  URL: https://eccc.weizmann.ac.il/report/2011/136/.
  * [GG17] Shafi Goldwasser and Ofer Grossman.  Bipartite perfect matching in pseudo-deterministic $\NC$.  In International Colloquium on Automata, Languages, and Programming _(ICALP)_ , pages 87:1–87:13, 2017.  doi:10.4230/LIPIcs.ICALP.2017.87.
  * [GG21] Sumanta Ghosh and Rohit Gurjar.  Matroid intersection: A pseudo-deterministic parallel reduction from search to weighted-decision.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques _(APPROX/RANDOM)_ , pages 41:1–41:16, 2021.  doi:10.4230/LIPIcs.APPROX/RANDOM.2021.41.
  * [GGH18] Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden.  Pseudo-deterministic proofs.  In Innovations in Theoretical Computer Science, _(ITCS)_ , pages 17:1–17:18, 2018.  doi:10.4230/LIPIcs.ITCS.2018.17.
  * [GGH19] Michel X. Goemans, Shafi Goldwasser, and Dhiraj Holden.  Doubly-efficient pseudo-deterministic proofs.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 26:135, 2019.  URL: https://eccc.weizmann.ac.il/report/2019/135.
  * [GGMW20] Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff.  Pseudo-deterministic streaming.  In Innovations in Theoretical Computer Science _(ITCS)_ , pages 79:1–79:25, 2020.  doi:10.4230/LIPIcs.ITCS.2020.79.
  * [GGR13] Oded Goldreich, Shafi Goldwasser, and Dana Ron.  On the possibilities and limitations of pseudodeterministic algorithms.  In Innovations in Theoretical Computer Science _(ITCS)_ , pages 127–138, 2013.  doi:10.1145/2422436.2422453.
  * [GIPS21] Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam.  On the pseudo-deterministic query complexity of $\NP$ search problems.  In Computational Complexity Conference _(CCC)_ , pages 36:1–36:22, 2021.  doi:10.4230/LIPIcs.CCC.2021.36.
  * [GKR15] Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum.  Delegating computation: interactive proofs for muggles.  Journal of the ACM, 62(4):27:1–27:64, 2015.  doi:10.1145/2699436.
  * [GL89] Oded Goldreich and Leonid A. Levin.  A hard-core predicate for all one-way functions.  In ACM Symposium on Theory of Computing _(STOC)_ , pages 25–32, 1989.  doi:10.1145/73007.73010.
  * [GL19] Ofer Grossman and Yang P. Liu.  Reproducibility and pseudo-determinism in Log-Space.  In Symposium on Discrete Algorithms _(SODA)_ , pages 606–620, 2019.  doi:10.1137/1.9781611975482.38.
  * [Gol08] Oded Goldreich.  Computational complexity: a conceptual perspective.  Cambridge University Press, 2008.  doi:10.1017/CBO9780511804106.
  * [Gol17] Oded Goldreich.  On the doubly-efficient interactive proof systems of GKR.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 24:101, 2017.  URL: https://eccc.weizmann.ac.il/report/2017/101.
  * [Gol18] Oded Goldreich.  On doubly-efficient interactive proof systems.  Foundations and Trends® in Theoretical Computer Science, 13(3):158–246, 2018.  doi:10.1561/0400000084.
  * [Gol19] Oded Goldreich.  Multi-pseudodeterministic algorithms.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 26:12, 2019.  URL: https://eccc.weizmann.ac.il/report/2019/012.
  * [Gro15] Ofer Grossman.  Finding primitive roots pseudo-deterministically.  Electronic Colloquium on Computational Complexity _(ECCC)_ , 22:207, 2015.  URL: https://eccc.weizmann.ac.il/report/2015/207.
  * [GS92] Peter Gemmell and Madhu Sudan.  Highly resilient correctors for polynomials.  Inf. Process. Lett., 43(4):169–174, 1992.  doi:10.1016/0020-0190(92)90195-2.
  * [HAB02] William Hesse, Eric Allender, and David A. Mix Barrington.  Uniform constant-depth threshold circuits for division and iterated multiplication.  J. Comput. Syst. Sci., 65(4):695–716, 2002.  doi:10.1016/S0022-0000(02)00025-9.
  * [HV06] Alexander Healy and Emanuele Viola.  Constant-depth circuits for arithmetic in finite fields of characteristic two.  In Symposium on Theoretical Aspects of Computer Science _(STACS)_ , volume 3884 of Lecture Notes in Computer Science, pages 672–683. Springer, 2006.  doi:10.1007/11672142\\_55.
  * [IKW02] Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.  In search of an easy witness: exponential time vs. probabilistic polynomial time.  J. Comput. Syst. Sci., 65(4):672–694, 2002.  doi:10.1016/S0022-0000(02)00024-7.
  * [IW97] Russell Impagliazzo and Avi Wigderson.  $\P=\BPP$ if $\E$ requires exponential circuits: Derandomizing the XOR lemma.  In ACM Symposium on Theory of Computing _(STOC)_ , pages 220–229. ACM, 1997.  doi:10.1145/258533.258590.
  * [IW01] Russell Impagliazzo and Avi Wigderson.  Randomness vs time: Derandomization under a uniform assumption.  Journal of Computer and System Sciences, 63(4):672–688, 2001.  doi:10.1006/jcss.2001.1780.
  * [Kan82] Ravi Kannan.  Circuit-size lower bounds and non-reducibility to sparse sets.  Inf. Control., 55(1-3):40–56, 1982.  doi:10.1016/S0019-9958(82)90382-5.
  * [KL80] Richard M. Karp and Richard J. Lipton.  Some connections between nonuniform and uniform complexity classes.  In ACM Symposium on Theory of Computing _(STOC)_ , pages 302–309, 1980.  doi:10.1145/800141.804678.
  * [LO87] J. C. Lagarias and Andrew M. Odlyzko.  Computing $\pi(x)$: An analytic method.  J. Algorithms, 8(2):173–191, 1987.  doi:10.1016/0196-6774(87)90037-X.
  * [LO22] Zhenjian Lu and Igor C. Oliveira.  Theory and applications of probabilistic Kolmogorov complexity.  Bull. EATCS, 137, 2022.  URL: http://bulletin.eatcs.org/index.php/beatcs/article/view/700.
  * [LOS21] Zhenjian Lu, Igor C. Oliveira, and Rahul Santhanam.  Pseudodeterministic algorithms and the structure of probabilistic time.  In ACM Symposium on Theory of Computing _(STOC)_ , pages 303–316, 2021.  doi:10.1145/3406325.3451085.
  * [LY22] Jiatu Li and Tianqi Yang.  $3.1n-o(n)$ circuit lower bounds for explicit functions.  In STOC, pages 1180–1193. ACM, 2022.  doi:10.1145/3519935.3519976.
  * [MVW99] Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe.  Super-polynomial versus half-exponential circuit size in the exponential hierarchy.  In International Computing and Combinatorics Conference _(COCOON)_ , volume 1627 of Lecture Notes in Computer Science, pages 210–220. Springer, 1999.  doi:10.1007/3-540-48686-0\\_21.
  * [NW94] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of Computer and System Sciences, 49(2):149–167, 1994.  doi:10.1016/S0022-0000(05)80043-1.
  * [Oli19] Igor C. Oliveira.  Randomness and intractability in Kolmogorov complexity.  In International Colloquium on Automata, Languages, and Programming _(ICALP)_ , pages 32:1–32:14, 2019.  doi:10.4230/LIPIcs.ICALP.2019.32.
  * [OS17] Igor C. Oliveira and Rahul Santhanam.  Pseudodeterministic constructions in subexponential time.  In Symposium on Theory of Computing _(STOC)_ , pages 665–677, 2017.  doi:10.1145/3055399.3055500.
  * [OS18] Igor C. Oliveira and Rahul Santhanam.  Pseudo-derandomizing learning and approximation.  In International Conference on Randomization and Computation _(RANDOM)_ , pages 55:1–55:19, 2018.  doi:10.4230/LIPIcs.APPROX-RANDOM.2018.55.
  * [Sho92] Victor Shoup.  Searching for primitive roots in finite fields.  Mathematics of Computation, 58(197):369–380, January 1992.  doi:10.1090/S0025-5718-1992-1106981-9.
  * [STV01] Madhu Sudan, Luca Trevisan, and Salil P. Vadhan.  Pseudorandom generators without the XOR lemma.  J. Comput. Syst. Sci., 62(2):236–266, 2001.  doi:10.1006/jcss.2000.1730.
  * [SU05] Ronen Shaltiel and Christopher Umans.  Simple extractors for all min-entropies and a new pseudorandom generator.  J. ACM, 52(2):172–216, 2005.  doi:10.1145/1059513.1059516.
  * [Sud95] Madhu Sudan.  Efficient Checking of Polynomials and Proofs anf the Hardness of Approximation Problems, volume 1001 of Lecture Notes in Computer Science.  Springer, 1995.  doi:10.1007/3-540-60615-7.
  * [Sud97] Madhu Sudan.  Decoding of Reed Solomon codes beyond the error-correction bound.  J. Complex., 13(1):180–193, 1997.  doi:10.1006/jcom.1997.0439.
  * [TCH12] Terence Tao, Ernest Croot, III, and Harald Helfgott.  Deterministic methods to find primes.  Math. Comp., 81(278):1233–1246, 2012.  doi:10.1090/S0025-5718-2011-02542-1.
  * [TV07] Luca Trevisan and Salil P. Vadhan.  Pseudorandomness and average-case complexity via uniform reductions.  Computational Complexity, 16(4):331–364, 2007.  doi:10.1007/s00037-007-0233-x.
  * [VL99] Jacobus Hendricus Van Lint.  Introduction to coding theory, volume 86.  Springer-Verlag Berlin Heidelberg, 1999.
  * [WDP+22] Jason Vander Woude, Peter Dixon, A. Pavan, Jamie Radcliffe, and N. V. Vinodchandran.  The geometry of rounding.  Electronic Colloquium on Computational Complexity _(ECCC)_ , TR22-160, 2022.  URL: https://eccc.weizmann.ac.il/report/2022/160.
  * [Yao82] Andrew Chi-Chih Yao.  Theory and applications of trapdoor functions (extended abstract).  In IEEE Symposium on Foundations of Computer Science _(FOCS)_ , pages 80–91, 1982.  doi:10.1109/SFCS.1982.45.