###  5.4 Proof of Theorem 3.6(II)

As in §4.3, we consider a more general restatement of Theorem 3.6(II) that is
better suitable for induction on $d$.

######  Main Theorem 3.6(II) (slightly more general restatement).

Let $P$ be a finite subgraph of $\mathsf{Path}_{\mathbb{Z}}$ and let $T$ be a
$P$-join tree of $\llbracket\hskip 0.59998pt\rrbracket$-depth $d$. Then

$\displaystyle\Psi(T)\geq\frac{1}{\sqrt{32\mathrm{e}}}d\lambda(P)^{1/2d}-d+\Delta(P).$

###### Proof.

We argue by induction on $d$. Here we treat $d=0$ as the base case, where $P$
is a single edge (or empty) and the bound $\Psi(T)\geq\Delta(P)$ is trivial.

For the induction step where $d\geq 1$, we reduce to the case $\Delta(P)=1$
exactly as in our proof of Theorem 3.6(I). We therefore assume that
$T=\llbracket T_{1},\dots,T_{m}\rrbracket$ is a $\mathsf{Path}_{k}$-join tree
of $\llbracket\hskip 0.59998pt\rrbracket$-depth $m$ and aim to show

(13) $\Psi(T)\geq\varepsilon dk^{1/2d}-d+1\quad\text{ where
}\quad\varepsilon\vcentcolon=\frac{1}{\sqrt{32\mathrm{e}}}.$

Let $G_{1}\cup\dots\cup G_{m}=\mathsf{Path}_{k}$ where $G_{j}$ is the root
graph of $T_{j}$, and let $g\vcentcolon=\mathrm{gap}(G_{1},\dots,G_{m})$. We
prove inequality (13) by considering three cases, according to whether
$\max_{j\in[m]}\lambda(G_{j})$ is:

greater than $\dfrac{\varepsilon^{2}k}{\Delta(G_{j})}$, between $\dfrac{g}{8}$
and $\dfrac{\varepsilon^{2}k}{\Delta(G_{j})}$, or less than $\dfrac{g}{8}$.

The most interesting is the third case, which relies on Lemma 5.10 (the
stronger version of Main Lemma 3.5(II)).

##### Case 1:

Assume there exists $j\in[m]$ such that
$\lambda(G_{j})\geq\displaystyle\frac{\varepsilon^{2}k}{\Delta(G_{j})}$.

By the induction hypothesis applied to $T_{j}$, we have

(14) $\displaystyle\Psi(T_{j})$
$\displaystyle\geq\varepsilon(d-1)\lambda(G_{j})^{1/(2d-2)}+\Delta(G_{j})-d+1$
$\displaystyle=(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G^{j})\right)^{1/(2d-2)}+\Delta(G_{j})-d+1.$

Therefore,

$\displaystyle\Psi(T)+d-1{}_{\vphantom{\big{|}}}$
$\displaystyle\geq\Psi(T_{j})+d-1$ (since clearly $\Psi(T)\geq\Psi(T_{j})$)
$\displaystyle\geq(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\right)^{1/(2d-2)}+\Delta(G_{j})$
(by induction hypothesis (14))
$\displaystyle\geq(2d-1)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\frac{\Delta(G_{j})}{2}\right)^{1/(2d-1)}+\frac{\Delta(G_{j})}{2}$
(by Lemma 3.10) $\displaystyle\geq
2d\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\frac{\Delta(G_{j})^{2}}{4}\right)^{1/2d}$
(by Lemma 3.10 again) $\displaystyle\geq
2d\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{\varepsilon^{2}}{4}k\right)^{1/2d}$
(since
$\lambda(G_{j})\geq\displaystyle\frac{\varepsilon^{2}k}{\Delta(G_{j})}\geq\displaystyle\frac{\varepsilon^{2}k}{\Delta(G_{j})^{2}}$)
$\displaystyle=\varepsilon dk^{1/2d}.$

##### Case 2:

Assume there exists $j\in[m]$ such that
$\displaystyle\frac{g}{8}\leq\lambda(G_{j})\leq\frac{\varepsilon^{2}k}{\Delta(G_{j})}.$

We have

$\displaystyle\Psi(T)+d-1$
$\displaystyle\geq\Psi(T_{j})+\vv\Delta(G_{1},\dots,G_{j-1},G_{j+1},\dots,G_{m}\mid
G_{j})+d-1$ (by Corollary 5.5)
$\displaystyle\geq(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\right)^{1/(2d-2)}+\vv\Delta(G_{j},G_{1},\dots,G_{j-1},G_{j+1},\dots,G_{m})$
(by induction hypothesis (14))
$\displaystyle\geq(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\right)^{1/(2d-2)}+\frac{(1-\varepsilon^{2})k}{4g}$
(by Lemma 5.8(iii)) $\displaystyle\geq
2d\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G_{j})\left(\frac{(1-\varepsilon^{2})k}{8g}\right)^{2}\right)^{1/2d}$
(by Lemma 3.10 twice) $\displaystyle\geq
2d\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{(1-\varepsilon^{2})^{2}}{64}k\right)^{1/2d}$
(since $\lambda(G_{j})\geq\frac{g}{8}$ and $k\geq g$)
$\displaystyle=\varepsilon
d\left(\frac{(1-\varepsilon^{2})^{2}}{16\varepsilon^{2}}k\right)^{1/2d}$
$\displaystyle\geq\varepsilon dk^{1/2d}$ $\displaystyle\text{(since
$\varepsilon=\frac{1}{\sqrt{32\mathrm{e}}}$)}.$

##### Case 3:

Assume $\displaystyle\lambda(G_{j})\leq\frac{g}{8}$ for all $j\in[m]$.

By Lemma 5.10 (the stronger version of Main Lemma 3.5(II)), there exists a
shift permutation $\sigma:[m]\stackrel{{\scriptstyle\cong}}{{\to}}[m]$ such
that

(15) $\displaystyle\vv{\lambda}(G_{\sigma(1)},\dots,G_{\sigma(m)})$
$\displaystyle\geq\frac{g-3\max_{j\in[m]}\lambda(G_{j})}{4}>\frac{g}{8},$ (16)
$\displaystyle\vv\Delta(G_{\widetilde{\sigma}_{j}(1)},\dots,G_{\widetilde{\sigma}_{j}(m)})$
$\displaystyle\geq\frac{k}{4g}\quad\text{ for all }j\in[m].$

For each $j\in[m]$, let

$\displaystyle j^{\star}$
$\displaystyle\vcentcolon=\sigma^{-1}(j),\vphantom{\Big{|}}$ $\displaystyle
F_{j}$ $\displaystyle\vcentcolon=G_{\sigma(1)}\cup\dots\cup
G_{\sigma(j^{\star}-1)}$ $\displaystyle({=}\
G_{\widetilde{\sigma}_{j}(1)}\cup\dots\cup
G_{\widetilde{\sigma}_{j}(j^{\star}-1)}),$ $\displaystyle G^{j}$
$\displaystyle\vcentcolon=G_{j}\ominus F_{j},\vphantom{\Big{|}}$
$\displaystyle T^{j}$ $\displaystyle\vcentcolon=T_{j}\ominus F_{j}$
$\displaystyle({=}\ T_{j}\textup{ restricted to }G^{j}).$

Note the inequality

(17)
$\displaystyle\vphantom{\Big{|}}\vv{\Delta}(G_{\widetilde{\sigma}_{j}(1)},\dots,G_{\widetilde{\sigma}_{j}(m)})$
$\displaystyle\geq\vv{\Delta}(G_{\widetilde{\sigma}_{j}(j^{\star})},\dots,G_{\widetilde{\sigma}_{j}(m)}\mid
G_{\widetilde{\sigma}_{j}(1)}\cup\dots\cup
G_{\widetilde{\sigma}_{j}(j^{\star}-1)})$
$\displaystyle=\vv{\Delta}(G_{\sigma(j^{\star})},\dots,G_{\sigma(m)}\mid
G_{\sigma(1)}\cup\dots\cup G_{\sigma(j-1)})$
$\displaystyle=\sum_{i=j^{\star}}^{m}\Delta(G^{\sigma(i)}).$

Also, applying the induction hypothesis to each $T^{j}$, we have

(18) $\displaystyle\Psi(T^{j})$
$\displaystyle\geq\varepsilon(d-1)\lambda(G^{j})^{1/(2d-2)}+\Delta(G^{j})-d+1.$

For each $j\in[m]$, we have

$\displaystyle\vphantom{\Big{|}}\Psi(T)+d-1$
$\displaystyle\geq\Psi(T^{j})-\Delta(G^{j})+\vv\Delta(G_{\widetilde{\sigma}_{j}(1)},\dots,G_{\widetilde{\sigma}_{j}(m)})+d-1$
(by Lemma 5.4(iii))
$\displaystyle\geq(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G^{j})\right)^{1/(2d-2)}+\vv\Delta(G_{\widetilde{\sigma}_{j}(1)},\dots,G_{\widetilde{\sigma}_{j}(m)})$
(by (18))
$\displaystyle\geq(2d-2)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\lambda(G^{j})\right)^{1/(2d-2)}+\frac{k}{8g}+\sum_{i=j^{\star}}^{m}\frac{\Delta(G^{\sigma(i)})}{2}$
(by $\tfrac{1}{2}$(16) $+$ $\tfrac{1}{2}$(17))
$\displaystyle\geq(2d-1)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{k}{8g}\lambda(G^{j})\right)^{1/(2d-1)}+\sum_{i=j^{\star}}^{m}\frac{\Delta(G^{\sigma(i)})}{2}$
$\displaystyle\text{(by Lemma \ref{la:numerical0})}.$

Maximizing over $j\in[m]$, we finally obtain the desired bound 13 using Lemma
3.9 (the key numerical inequality) as follows:

$\displaystyle\Psi(T)+d-1$ $\displaystyle\geq\max_{j\in[m]}\
(2d-1)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{k}{8g}\lambda(G^{j})\right)^{1/(2d-1)}+\sum_{i=j^{\star}}^{m}\frac{\Delta(G^{\sigma(i)})}{2}$
$\displaystyle=\max_{h\in[m]}\
(2d-1)\left(\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{k}{8g}\lambda(G^{\sigma(h)})\right)^{1/(2d-1)}+\sum_{i=h}^{m}\frac{\Delta(G^{\sigma(h)})}{2}$
$\displaystyle\geq
2d\left(\frac{1}{\mathrm{e}}\sum_{h=1}^{m}\left(\frac{\varepsilon}{2}\right)^{2d-2}\frac{k}{8g}\lambda(G^{\sigma(h)})\frac{\Delta(G^{\sigma(h)})}{2}\right)^{1/2d}$
(by Lemma 3.9) $\displaystyle=\varepsilon
d\left(\frac{k}{4\mathrm{e}\varepsilon^{2}g}\vv{\lambda\Delta}(G_{\sigma(1)},\dots,G_{\sigma(m)})\right)^{1/2d}$
$\displaystyle\geq\varepsilon
d\left(\frac{k}{4\mathrm{e}\varepsilon^{2}g}\vv{\lambda}(G_{\sigma(1)},\dots,G_{\sigma(m)})\right)^{1/2d}$
$\displaystyle\geq\varepsilon
d\left(\frac{k}{32\mathrm{e}\varepsilon^{2}}\right)^{1/2d}$ (by (15))
$\displaystyle=\varepsilon dk^{1/2d}.$

##  6 Tradeoffs for pathsets

In this section, we review the Pathset Framework of papers [15, 21, 23, 24]
and prove new tradeoffs for pathset complexity (Theorem 6.11) that follow from
our tradeoffs for join trees (Theorem 3.6).

###  6.1 Relations and joins

Throughout this section, we fix arbitrary positive integers $k$ and $n$. We
additionally fix an arbitrary parameter $\tilde{n}\leq n$. In our application,
we will set $\tilde{n}\vcentcolon=n^{(k-1)/k}$.

######  Definition 6.1 ($G$-relations).

For a graph $G\subseteq\mathsf{Path}_{k}$, we refer to sets
$\mathcal{A}\subseteq[n]^{V(G)}$ as $G$-relations. We denote the set of all
$G$-relations by $\mathscr{R}_{G}$. (That is, $\mathscr{R}_{G}$ is the set of
“$V(G)$-ary” relations on $[n]$.)

The join operation $\bowtie$ combines a $G$-relation and an $H$-relation into
a $G\cup H$-relation.

######  Definition 6.2 (Join).

For graphs $G,H\subseteq\mathsf{Path}_{k}$ and relations
$\mathcal{A}\in\mathscr{R}_{G}$ and $\mathcal{B}\in\mathscr{R}_{H}$, the join
of $\mathcal{A}$ and $\mathcal{B}$ is the relation
$\mathcal{A}\bowtie\mathcal{B}\in\mathscr{R}_{G\cup H}$ defined by

$\displaystyle\mathcal{A}\bowtie\mathcal{B}$
$\displaystyle\vcentcolon=\\{\gamma\in[n]^{V(G)\cup
V(H)}:\gamma_{V(G)}\in\mathcal{A}\text{ and }\gamma_{V(H)}\in\mathcal{B}\\}.$

Note that the join behaves as direct product $\mathcal{A}\times\mathcal{B}$
when $V(G)\cap V(H)=\emptyset$, and as intersection
$\mathcal{A}\cap\mathcal{B}$ when $V(G)=V(H)$.

###  6.2 Density and pathsets

######  Definition 6.3 (Density).

Let $G\subseteq\mathsf{Path}_{k}$. The density of a relation
$\mathcal{A}\in\mathscr{R}_{G}$ is defined by

$\displaystyle\mu(\mathcal{A})$
$\displaystyle\vcentcolon=\frac{|\mathcal{A}|}{n^{|V(G)|}}$
$\displaystyle=\operatorname*{\mathds{P}}_{\alpha\in[n]^{V(G)}}[\
\alpha\in\mathcal{A}\ ].$ For a graph $F\subseteq\mathsf{Path}_{k}$ and
$I=V(F)\cap V(G)$, the maximum density of $\mathcal{A}$ conditioned on $F$ is
defined by $\displaystyle\mu(\mathcal{A}\mid F)$
$\displaystyle\vcentcolon=\max_{\beta\in[n]^{V(F)}}\frac{|\\{\alpha\in\mathcal{A}:\alpha_{I}=\beta_{I}\\}|}{n^{|V(G)\setminus
V(F)|}}$ $\displaystyle=\max_{\beta\in[n]^{V(F)}}\
\operatorname*{\mathds{P}}_{\alpha\in[n]^{V(G)}}[\ \alpha\in\mathcal{A}\ |\
\alpha_{I}=\beta_{I}\ ].$

(Note that
$0\leq\mu(\mathcal{A})=\mu(\mathcal{A}\mid\emptyset)\leq\mu(\mathcal{A}\mid
F)\leq 1$.)

The next lemma and corollary relate the density of a join to the maximum
conditional densities of the constituent relations. The proof is another
simple exercise in relational algebra.

######  Lemma 6.4 (Chain rule for density of a join).

For all graphs $F,G,H\subseteq\mathsf{Path}_{k}$ and relations
$\mathcal{A}\in\mathscr{R}_{G}$ and $\mathcal{B}\in\mathscr{R}_{H}$, we have

$\displaystyle\mu(\mathcal{A}\bowtie\mathcal{B}\mid F)$
$\displaystyle\leq\mu(\mathcal{A}\mid F)\cdot\mu(\mathcal{B}\mid F\cup G).$

######  Corollary 6.5 ($m$-ary version of Lemma 6.4).

For all graphs $G_{1},\dots,G_{m}\subseteq\mathsf{Path}_{k}$ and relations
$\mathcal{A}_{j}\in\mathscr{R}_{G_{j}}$ ($j\in[m]$), we have

$\displaystyle\mu(\mathcal{A}_{1}\bowtie\cdots\bowtie\mathcal{A}_{m})$
$\displaystyle\leq\,\prod_{j=1}^{m}\>\mu(\mathcal{A}_{j}\mid
G_{1}\cup\dots\cup G_{j-1}).$

Furthermore, since the density of the join does not depend on the ordering of
relations $\mathcal{A}_{1},\dots,\mathcal{A}_{m}$, we have

$\displaystyle\mu(\mathcal{A}_{1}\bowtie\cdots\bowtie\mathcal{A}_{m})$
$\displaystyle\leq\prod_{j=1}^{m}\>\mu(\mathcal{A}_{\pi(j)}\mid
G_{\pi(1)}\cup\dots\cup G_{\pi(j-1)})$

for every permutation
$\smash{\pi:[m]\stackrel{{\scriptstyle\cong}}{{\to}}[m]}$.

The lifting technique of papers [21, 23] focuses on a special class of
$G$-relations that are subject to a family of density constraints in terms of
$\Delta(\cdot|\cdot)$.

######  Definition 6.6 ($G$-pathsets).

For a graph $G\subseteq\mathsf{Path}_{k}$, a $G$-pathset (with respect to
parameters $n$ and $\tilde{n}$) is a relation $\mathcal{A}\in\mathscr{R}_{G}$
such that for all graphs $F\subseteq\mathsf{Path}_{k}$,

$\displaystyle\mu(\mathcal{A}\mid F)\leq(1/\tilde{n})^{\Delta(G\,\mid\,F)}.$

The set of $G$-pathsets is denoted by $\mathscr{P}_{G}$. (Note that
$\mathscr{P}_{G}$ is a proper subset of $\mathscr{R}_{G}$ when $G$ is
nonempty.)

The next result (Corollary 6.5 applied to pathsets) bounds the density of a
join of pathsets in terms of the operation $\vv\Delta(\cdot)$.

######  Corollary 6.7.

For all graphs $G_{1},\dots,G_{m}\subseteq\mathsf{Path}_{k}$ and pathsets
$\mathcal{A}_{j}\in\mathscr{P}_{G_{j}}$ ($j\in[m]$), we have

$\displaystyle\mu(\mathcal{A}_{1}\bowtie\cdots\bowtie\mathcal{A}_{m})$
$\displaystyle\leq\,\min_{\pi\,:\,[m]\,\stackrel{{\scriptstyle\cong}}{{\to}}\,[m]}\>(1/\tilde{n})^{\vv\Delta(G_{\pi(1)},\dots,G_{\pi(m)})}.$

###  6.3 Pathset complexity

For a graph $G\subseteq\mathsf{Path}_{k}$, we define a family of complexity
measures $\mu_{T}:\mathscr{P}_{G}\to\mathbb{N}$ for each $G$-join tree $T$.

######  Definition 6.8 (Pathset complexity).

Let $G\subseteq\mathsf{Path}_{k}$, let $\mathcal{A}\in\mathscr{P}_{G}$, and
let $T$ be a $G$-join tree. The $T$-pathset complexity of $\mathcal{A}$,
denoted by $\chi_{T}(\mathcal{A})$, is defined inductively as follows:

  * •

If $T$ is a single node labeled by $G$ (in which case $\|G\|\leq 1$), then

$\displaystyle\chi_{T}(\mathcal{A})$
$\displaystyle\vcentcolon=\begin{cases}0&\text{if $\|G\|=0$ or $\mathcal{A}$
is empty},\\\ 1&\text{if $\|G\|=1$ and $\mathcal{A}$ is nonempty}.\end{cases}$

  * •

If $T=\langle T_{1},T_{2}\rangle$ where $T_{1},T_{2}$ are $G_{1},G_{2}$-join
trees, then

$\displaystyle\chi_{T}(\mathcal{A})$
$\displaystyle\vcentcolon=\min_{\begin{subarray}{c}\vphantom{\big{|}}\text{sequences
}\\{(\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i})\\}_{i}\,:\\\
\vphantom{|}\smash{(\mathcal{A}_{i},\mathcal{B}_{i},\mathcal{C}_{i})\,\in\,\mathscr{P}_{G}\times\mathscr{P}_{G_{1}}\times\mathscr{P}_{G_{2}}},\\\
\vphantom{\big{|}}\mathcal{A}_{i}\,\subseteq\,\mathcal{B}_{i}\,\bowtie\,\mathcal{C}_{i},\
\mathcal{A}\,\subseteq\,\bigcup_{i}\mathcal{A}_{i}\end{subarray}}\,\sum_{i}\
\max\\{\chi_{T_{1}}(\mathcal{B}_{i}),\,\chi_{T_{2}}(\mathcal{C}_{i})\\}.$

Here $i$ ranges over an arbitrary finite index set.

The following lower bound on pathset complexity was first proved in [23], then
again in [15] with an improved big-$\Omega$ constant.

######  Theorem 6.9 ([15, 23]).

For every $\mathsf{Path}_{k}$-join tree $T$ and $\mathsf{Path}_{k}$-pathset
$\mathcal{A}$,

$\displaystyle\chi_{T}(\mathcal{A})\geq\tilde{n}^{\Omega(\log
k)}\cdot\mu(\mathcal{A}).$

###  6.4 Lower bounds on pathset complexity

The main results of this section (Theorem 6.11 and Corollary 6.12) give
tradeoffs for pathset complexity $\chi_{T}(\mathcal{A})$ with respect to the
$\langle\\!\langle\rangle\\!\rangle$\- and $\llbracket\hskip
0.59998pt\rrbracket$-depth of the join tree $T$. These lower bounds are based
on the following lemma.

######  Lemma 6.10.

For every $\mathsf{Path}_{k}$-join tree $T$ and $\mathsf{Path}_{k}$-pathset
$\mathcal{A}$,

$\displaystyle\chi_{T}(\mathcal{A})\geq\tilde{n}^{\Psi(T)}\cdot\mu(\mathcal{A}).$

###### Proof.

Fix an enumerate $G_{1},\dots,G_{m}$ of a $T$-branch covering of
$\mathsf{Path}_{k}$ such that $\Psi(T)=\vv\Delta(G_{1},\dots,G_{m})$. We first
observe that pathset complexity $\chi_{T}(\mathcal{A})$ is invariant under
rotations of $T$, that is, exchanging the left and right children of any
subtree. Noting that the theorem statement has nothing to do with
$\langle\\!\langle\rangle\\!\rangle$-depth (which is obviously not invariant
under rotations), we may assume without loss of generality that
$\\{G_{1},\dots,G_{m}\\}$ is the $T$-branch covering associated with the right
spine of $T$. That is, assume that $T=\langle\\!\langle
T_{1},\dots,T_{m}\rangle\\!\rangle$ where each $T_{j}$ is a $B_{j}$-join tree
and $(G_{1},\dots,G_{m})=(B_{\pi(1)},\dots,B_{\pi(m)})$ for some permutation
$\smash{\pi:[m]\stackrel{{\scriptstyle\cong}}{{\to}}[m]}$.

For each $j\in[m]$, let

$\displaystyle A_{j}\vcentcolon=B_{j}\cup\dots\cup B_{m},\qquad
S_{j}\vcentcolon=\langle\\!\langle T_{j},\dots,T_{m}\rangle\\!\rangle.$

Note that $S_{j}$ is an $A_{j}$-join tree. In the case $j=1$, we have
$S_{1}=T$ and $A_{1}=\mathsf{Path}_{k}$.

By definition of pathset complexity, for all $j\in[m-1]$ and indices
$i_{1},\dots,i_{j-1}$, there exist nonempty pathsets
$\mathcal{A}_{i_{1},\dots,i_{j-1}}\in\mathscr{P}_{A_{j}}$ and
$\mathcal{B}_{i_{1},\dots,i_{j}}\in\mathscr{P}_{B_{j}}$ such that, letting
$\mathcal{A}_{()}\vcentcolon=\mathcal{A}$, for all $j\in[m-1]$, we have

$\displaystyle\mathcal{A}_{i_{1},\dots,i_{j-1}}$
$\displaystyle\subseteq\>\bigcup_{i_{j}}\
(\mathcal{B}_{i_{1},\dots,i_{j}}\bowtie\mathcal{A}_{i_{1},\dots,i_{j}}),$
$\displaystyle\chi_{S_{j}}(\mathcal{A}_{i_{1},\dots,i_{j-1}})$
$\displaystyle=\sum_{i_{j}}\
\max\\{\chi_{T_{j}}(\mathcal{B}_{i_{1},\dots,i_{j}}),\,\chi_{S_{j+1}}(\mathcal{A}_{i_{1},\dots,i_{j}})\\}.$

It follows that

$\displaystyle\chi_{T}(\mathcal{A})=\chi_{S_{1}}(\mathcal{A}_{()})\geq\sum_{i_{1}}\chi_{S_{2}}(\mathcal{A}_{i_{1}})\geq\sum_{i_{1},i_{2}}\chi_{S_{3}}(\mathcal{A}_{i_{1},i_{2}})\geq\cdots\geq\sum_{i_{1},\dots,i_{m-1}}\chi_{S_{m}}(\mathcal{A}_{i_{1},\dots,i_{j-1}})=\sum_{i_{1},\dots,i_{m-1}}1.$

Similarly, letting
$\mathcal{B}_{i_{1},\dots,i_{m-1},1}\vcentcolon=\mathcal{A}_{i_{1},\dots,i_{m-1}}$,
we have

$\displaystyle\mathcal{A}=\mathcal{A}_{()}\subseteq\>\bigcup_{i_{1}}\
\mathcal{B}_{i_{1}}\bowtie\mathcal{A}_{i_{1}}\>$
$\displaystyle\subseteq\>\bigcup_{i_{1}}\ \mathcal{B}_{i_{1}}\bowtie\
\bigcup_{i_{2}}\
\mathcal{B}_{i_{1},i_{2}}\bowtie\mathcal{A}_{i_{1},i_{2}}\>\subseteq\>\cdots$
$\displaystyle\cdots\>$ $\displaystyle\subseteq\>\bigcup_{i_{1}}\
\mathcal{B}_{i_{1}}\bowtie\ \bigcup_{i_{2}}\ \mathcal{B}_{i_{1},i_{2}}\bowtie\
\bigcup_{i_{3}}\ \mathcal{B}_{i_{1},i_{2},i_{3}}\bowtie\cdots\bowtie\
\bigcup_{\\!\\!\\!\\!i_{m-1}\\!\\!\\!\\!}\
\mathcal{B}_{i_{1},\dots,i_{m-1}}\bowtie\mathcal{A}_{i_{1},\dots,i_{m-1}}$
$\displaystyle=\>\bigcup_{\begin{subarray}{c}i_{1},\dots,i_{m-1}\\\
i_{m}=1\end{subarray}}\mathcal{B}_{i_{1}}\bowtie\mathcal{B}_{i_{1},i_{2}}\bowtie\mathcal{B}_{i_{1},i_{2},i_{3}}\bowtie\cdots\bowtie\mathcal{B}_{i_{1},\dots,i_{m-1}}\bowtie\mathcal{B}_{i_{1},\dots,i_{m}}.$

We may now bound $\mu(\mathcal{A})$ as follows.

$\displaystyle\mu(\mathcal{A})$
$\displaystyle\leq\sum_{\begin{subarray}{c}i_{1},\dots,i_{m-1}\\\
i_{m}=1\end{subarray}}\,\mu(\mathcal{B}_{i_{1}}\bowtie\mathcal{B}_{i_{1},i_{2}}\bowtie\mathcal{B}_{i_{1},i_{2},i_{3}}\bowtie\cdots\bowtie\mathcal{B}_{i_{1},\dots,i_{m}})$
$\displaystyle\leq\sum_{\begin{subarray}{c}i_{1},\dots,i_{m-1}\\\
i_{m}=1\end{subarray}}\,\prod_{j=1}^{m}\,\mu(\mathcal{B}_{i_{1},i_{2},\dots,i_{\pi(j)}}\mid
B_{\pi(1)}\cup B_{\pi(2)}\cup\dots\cup B_{\pi(j-1)})\quad\ \text{(by Corollary
\ref{cor:density})}$
$\displaystyle\leq\sum_{\begin{subarray}{c}i_{1},\dots,i_{m-1}\\\
i_{m}=1\end{subarray}}\,\prod_{j=1}^{m}\,(1/\tilde{n})^{\Delta(B_{\pi(j)}\,\mid\,B_{\pi(1)}\cup
B_{\pi(2)}\cup\dots\cup B_{\pi(j-1)})}\quad\ \text{(since each
$\mathcal{B}_{i_{1},i_{2},\dots,i_{\pi(j)}}$ is a $B_{\pi(j)}$-pathset)}$
$\displaystyle=(1/\tilde{n})^{\vv\Delta(B_{\pi(1)},\dots,B_{\pi(m)})}\cdot\sum_{\begin{subarray}{c}i_{1},\dots,i_{m-1}\\\
i_{m}=1\end{subarray}}1\ \ \leq\ \
(1/\tilde{n})^{\vv\Delta(B_{\pi(1)},\dots,B_{\pi(m)})}\cdot\chi_{T}(\mathcal{A}).$

Since $(B_{\pi(1)},\dots,B_{\pi(m)})=(G_{1},\dots,G_{m})$, we get the desired
bound

$\displaystyle\chi_{T}(\mathcal{A})\ \ $ $\displaystyle\geq\ \
\tilde{n}^{\vv\Delta(G_{1},\dots,G_{m})}\cdot\mu(\mathcal{A})\ \ =\ \
\tilde{n}^{\Psi(T)}\cdot\mu(\mathcal{A}).\qed$

As an immediate corollary of Lemma 6.10 and Theorem 3.6, we get the following
tradeoff for pathset complexity.

######  Theorem 6.11 (Pathset complexity tradeoffs).

For every $\mathsf{Path}_{k}$-join tree $T$ and $\mathsf{Path}_{k}$-pathset
$\mathcal{A}$,

  1. (I)

$\displaystyle\vphantom{\Big{|}}\smash{\chi_{T}(\mathcal{A})\geq\tilde{n}^{\frac{1}{30\mathrm{e}}dk^{1/d}-d}\cdot\mu(\mathcal{A})}$

where $d$ is the $\langle\\!\langle\rangle\\!\rangle$-depth of $T$,

  2. (II)

$\vphantom{\big{|}}\displaystyle\smash{\chi_{T}(\mathcal{A})\geq\tilde{n}^{\frac{1}{\sqrt{32\mathrm{e}}}dk^{1/2d}-d}\cdot\mu(\mathcal{A})}$

where $d$ is the $\llbracket\hskip 0.59998pt\rrbracket$-depth of $T$.

We remark that Theorem 6.11 does not imply Theorem 6.9, since the bounds of
Theorem 6.11 are trivial for $d=\Omega(k)$ while Theorem 6.9 applies to join
trees of arbitrary $\langle\\!\langle\rangle\\!\rangle$\- and
$\llbracket\hskip 0.59998pt\rrbracket$-depth. The “maximally overlapping”
$\mathsf{Path}_{k}$-join tree provides an example which has
$\langle\\!\langle\rangle\\!\rangle$\- and $\llbracket\hskip
0.59998pt\rrbracket$-depth $k-1$ and $\Psi$-value $1$. Together these bounds
imply:

######  Corollary 6.12.

Suppose that $\tilde{n}=n^{\Omega(1)}$ (for example,
$\tilde{n}=n^{1-\frac{1}{k}}$ in our application in this paper). Then for
every $\mathsf{Path}_{k}$-join tree $T$ and $\mathsf{Path}_{k}$-pathset
$\mathcal{A}$,

  1. (I)

$\displaystyle\vphantom{\Big{|}}\smash{\chi_{T}(\mathcal{A})\geq
n^{\Omega(d(k^{1/d}-1))}\cdot\mu(\mathcal{A})}$

where $d$ is the $\langle\\!\langle\rangle\\!\rangle$-depth of $T$,

  2. (II)

$\vphantom{\big{|}}\displaystyle\smash{\chi_{T}(\mathcal{A})\geq
n^{\Omega(d(k^{1/2d}-1))}\cdot\mu(\mathcal{A})}$

where $d$ is the $\llbracket\hskip 0.59998pt\rrbracket$-depth of $T$.

The lower bounds of Corollary 6.12 are asymptotically tight for every fixed
$d$ and $k$, and both bounds converge to $n^{\Omega(\log k)}$ since
$d(k^{1/d}-1)$ converges to $\ln k$ as $d\to\infty$.

##  7 Tradeoffs for $\mathit{AC^{0}}$ and $\mathit{SAC^{0}}$ formulas

In this section we prove Theorem 1.6, our size-depth tradeoffs for
$\mathit{SAC^{0}}$ and $\mathit{AC^{0}}$ formulas in both the monotone and
non-monotone settings. In §7.1 we discuss two different ways of converting
$\mathit{SAC^{0}}$ and $\mathit{AC^{0}}$ formula to DeMorgan formulas with
binary $\wedge$ and $\vee$ gates. We then prove tradeoff (I)+ over the course
of §7.2–7.5. At a high-level, the proof is a reduction that starts out with a
monotone $\mathit{SAC^{0}}$ formula of $\bigwedge$-depth $d$ and size $s$
computing $\textup{{sub-pmm}}_{n,k}$. The reduction extracts a
$\mathsf{Path}_{k}$-join tree $T$ of
$\langle\\!\langle\rangle\\!\rangle$-depth $d$ and a
$\mathsf{Path}_{k}$-pathset $\mathcal{A}\subseteq[n]^{\\{0,\dots,k\\}}$ of
density $n^{-O(1)}$ such that $\chi_{T}(\mathcal{A})\leq n^{O(1)}\cdot s$. On
the other hand, the pathset complexity lower bound of §6 (Corollary 6.12)
implies
$\chi_{T}(\mathcal{A})=n^{\smash{\Omega(dk^{1/d})}}\cdot\mu(\mathcal{A})$.
Combining these inequalities, we get the desired size lower bound
$s=n^{\Omega(dk^{1/d})-O(1)}$ ($=n^{\Omega(dk^{1/d})}$ since $dk^{1/d}\geq\log
k$).

We next prove tradeoff (II)- for non-monotone $\mathit{AC^{0}}$ formulas in
§7.6–7.8 via a novel reduction that makes a surprising connection between
$\mathit{AC^{0}}$ formula depth to $\llbracket\hskip
0.59998pt\rrbracket{}$-depth of join trees. The remaining two tradeoffs (I)-
and (II)+ of Theorem 1.6 (for non-monotone $\mathit{SAC^{0}}$ formulas and
monotone $\mathit{AC^{0}}$ formulas) are proved by a “convex combination” of
arguments in the proofs of (I)+ of (II)-. We omit the redundant details.

######  Proviso 7.1.

Throughout this section, we assume that $d\leq\log k$ and either
$k\leq\log\log n$ or $k\leq\log^{\ast}n$ in the monotone and non-monotone
settings, respectively. In all statements involving pathsets and pathset
complexity, the density parameter $\tilde{n}$ is fixed to $n^{(k-1)/k}$.

###  7.1 Converting $\mathit{AC^{0}}$ formulas to DeMorgan formulas

######  Definition 7.2 (DeMorgan formulas).

A DeMorgan formula is a rooted binary tree with non-leafs (“gates”) labeled by
$\wedge$ or $\vee$, and leaves (“inputs”) labeled by constants or literals. As
with $\mathit{AC^{0}}$ formulas, we measure size by the number of inputs
labeled by literals and depth (resp. $\wedge$-depth) by the maximum number of
gates (resp. $\wedge$-gates) on a root-to-leaf branch. Additionally, we define
left-depth (resp. $\wedge$-left-depth) of a DeMorgan formula as the maximum
number of left descents (resp. left descents at $\wedge$-gates) on a root-to-
leaf branch.

Our tradeoffs for $\mathit{SAC^{0}}$ and $\mathit{AC^{0}}$ formulas involve
two different ways of converting an $\mathit{(S)}\mathit{AC^{0}}$ formula F to
an equivalent DeMorgan formula f.

######  Definition 7.3 (DeMorgan conversions of $\mathit{AC^{0}}$ formulas).

  * •

The right-deep DeMorgan conversion of an $\mathit{AC^{0}}$ formula F is the
DeMorgan formula f obtained by replacing each $m$-ary each fan-in $m$
$\bigvee$ / $\bigwedge$ gate with a right-deep tree of $m-1$ binary $\vee$ /
$\wedge$ gates.

For example, if $\textup{{F}}=\bigwedge_{i=1}^{8}\textup{{F}}_{i}$, then its
right-deep DeMorgan conversion is the formula

$\displaystyle\textup{{f}}=\textup{{f}}_{1}\wedge(\textup{{f}}_{2}\wedge(\textup{{f}}_{3}\wedge(\textup{{f}}_{4}\wedge(\textup{{f}}_{5}\wedge(\textup{{f}}_{6}\wedge(\textup{{f}}_{7}\wedge\textup{{f}}_{8}))))))$

where each $\textup{{f}}_{i}$ is the right-deep DeMorgan conversion of
$\textup{{F}}_{i}$.

  * •

The balanced DeMorgan conversion of an $\mathit{AC^{0}}$ formula F is the
DeMorgan formula f obtained by replacing each $m$-ary each fan-in $m$
$\bigvee$ / $\bigwedge$ gate with a balanced tree of $m-1$ binary $\vee$ /
$\wedge$ gates.

For example, if $\textup{{F}}=\bigwedge_{i=1}^{8}\textup{{F}}_{i}$, then its
balanced DeMorgan conversion is the formula

$\displaystyle\textup{{f}}=((\textup{{f}}_{1}\vee\textup{{f}}_{2})\vee(\textup{{f}}_{3}\vee\textup{{f}}_{4}))\vee((\textup{{f}}_{5}\vee\textup{{f}}_{6})\vee(\textup{{f}}_{7}\vee\textup{{f}}_{8}))$

where each $\textup{{f}}_{i}$ is the balanced DeMorgan conversion of
$\textup{{F}}_{i}$.

Note that if F has depth $d$ and fan-in $m$, then its balanced DeMorgan
conversion has depth at most $d\lceil\log m\rceil$. If F has $\bigwedge$-fan-
in $d$ and $\bigwedge$-fan-in $m$, then its right-deep DeMorgan conversion has
$\wedge$-left-depth $d$ and $\wedge$-depth at most $dm$ (though possibly much
greater depth). Both conversions preserve size.

Our first tradeoff for $\mathit{SAC^{0}}$ formulas (§7.2–7.5) uses the right-
deep DeMorgan conversion to establish a connection between $\bigwedge$-fan-in,
$\wedge$-left-depth, and $\langle\\!\langle\rangle\\!\rangle$-depth of join
trees. Our second tradeoff for $\mathit{AC^{0}}$ formulas (§7.6–7.8) relies on
a randomized version of the balanced DeMorgan conversion to establish a
connection between $\mathit{AC^{0}}$ depth and $\llbracket\hskip
0.59998pt\rrbracket{}$-depth of join trees. We state the definition here, but
postpone analysis to §7.6.

######  Definition 7.4 (Randomized balanced DeMorgan conversion).

Let $t\in\mathbb{N}$ be an arbitrary parameter. For every $\mathit{AC^{0}}$
formula F, we define a random DeMorgan formula f with distribution
$\mathscr{D}_{t}(\textup{{F}})$ as follows:

  * •

If F has depth $0$ (i.e., is a constant or literal), then
$\textup{{f}}=\textup{{F}}$ (with probability $1$).

  * •

Suppose that F is $\bigwedge_{i=1}^{m}\textup{{F}}_{i}$ (resp.
$\bigvee_{i=1}^{m}\textup{{F}}_{i}$). Sample independent random DeMorgan
formulas $\textup{{f}}_{i}\sim\mathscr{D}_{t}(\textup{{F}}_{i})$ and
independent uniform random indices $\bm{i}_{1},\dots,\bm{i}_{tm}\in[m]$. Now
let f be the DeMorgan formula consisting of a balanced tree of $tm-1$ binary
$\wedge$-gates (resp. $\vee$-gates) with subformulas
$\textup{{f}}_{\bm{i}_{1}},\dots,\textup{{f}}_{\bm{i}_{tm}}$ feeding in.

Note that if F has depth $d$ and size $s$, then every f in the support of
$\mathscr{D}_{t}(\textup{{F}})$ has depth at most $d\lceil\log(ts)\rceil$ and
size at most $t^{d}s$. In particular, if $t=(\log s)^{O(1)}$ and
$d=o(\frac{\log s}{\log\log s})$, then f has size $s^{1+o(1)}$. Also note that
f does not necessarily compute the same function as F. However, for
$t\geq(\log s)^{2}$, we at least ensure that $\textup{{f}}(x)=\textup{{F}}(x)$
with high probability for any given input $x$.

We conclude this subsection with a few remarks on notation.

######  Notation 7.5.

Throughout this section, we speak of both $\mathit{AC^{0}}$ and DeMorgan
formulas on both $kn^{2}$ variables and $k$ variables. To keep these objects
straight, we consistently write

  * •

F for an $\mathit{AC^{0}}$ formula on $kn^{2}$ variables,

  * •

f for a DeMorgan formula on $kn^{2}$ variables,

  * •

G for an $\mathit{AC^{0}}$ formula on $k$ variables,

  * •

g for a DeMorgan formula on $k$ variables.

We use typewriter font $\textup{{F}},\textup{{f}}$ and
$\textup{{G}},\textup{{g}}$ to distinguish these formulas from the Boolean
functions of $kn^{2}$ and $k$ variables that they compute, denoted by italic
$f$ and $g$.

In the context of tradeoffs (I)±, we refer to F as an “$\mathit{SAC^{0}}$
formula” whenever we assume that it has $\bigwedge$-fan-in at most $n^{1/k}$.

######  Notation 7.6.

Note the distinction between syntactic equality of formulas (notated with $=$)
and semantic equivalence of formulas (notated with $\equiv$). For example,
$\textup{{f}}_{1}=\textup{{f}}_{2}$ expresses that $\textup{{f}}_{1}$ and
$\textup{{f}}_{2}$ are isomorphic as labeled binary trees, whereas
$\textup{{g}}_{1}\equiv\textup{{g}}_{2}$ expresses that $\textup{{g}}_{1}$ and
$\textup{{g}}_{2}$ compute the same Boolean function
$\\{0,1\\}^{k}\to\\{0,1\\}$. We sometimes write $\equiv$ between an
$\mathit{AC^{0}}$ formula and an equivalent DeMorgan formula (e.g.,
$\textup{{F}}\equiv\textup{{f}}$ or $\textup{{G}}\equiv\textup{{g}}$).

###  7.2 Monotone functions on $kn^{2}$ variables

In the context of problems $\textup{{bmm}}_{n,k}$, $\textup{{sub-pmm}}_{n,k}$,
$\textup{{pmm}}_{n,k}$, we identify elements of $\\{0,1\\}^{kn^{2}}$ with
$k$-tuples $\vec{M}=(M^{(1)},\dots,M^{(k)})$ of Boolean matrices
$M^{(i)}\in\\{0,1\\}^{n\times n}$. However, for purposes of our lower bound
method, it is convenient to instead identify $\\{0,1\\}^{kn^{2}}$ with the set
of subgraphs of the $n$-blow-up of $\mathsf{Path}_{k}$, defined below.

######  Definition 7.7 (The $n$-blow-up of a graph).

The $n$-blow-up of a graph $G$, denoted $G^{\uparrow n}$, is the graph with
vertex and edge sets

$\displaystyle V(G^{\uparrow n})$ $\displaystyle\vcentcolon=\\{v^{(a)}:v\in
V(G),\ a\in[n]\\}\quad\text{(a way of writing $V(G)\times[n]$)},$
$\displaystyle E(G^{\uparrow n})$
$\displaystyle\vcentcolon=\\{\\{v^{(a)},w^{(b)}\\}:\\{v,w\\}\in E(G),\
a,b\in[n]\\}.$

That is, for each vertex $v$ of $G$, the blow-up contains $n$ distinct
vertices named $v^{(1)},\dots,v^{(n)}$; and for each edge $\\{v,w\\}$ of $G$,
the blow-up contains the complete bipartite graph between sets
$\\{v^{(1)},\dots,v^{(n)}\\}$ and $\\{w^{(1)},\dots,w^{(n)}\\}$.

For $\alpha\in[n]^{V(G)}$, we write $G^{(\alpha)}$ for the isomorphic copy of
$G$ with

$\displaystyle V(G^{(\alpha)})$
$\displaystyle\vcentcolon=\\{v^{(\alpha_{v})}:v\in V(G)\\},$ $\displaystyle
E(G^{(\alpha)})$
$\displaystyle\vcentcolon=\\{\\{v^{(\alpha_{v})},w^{(\alpha_{w})}\\}:\\{v,w\\}\in
E(G)\\}.$

Graphs $G^{(\alpha)}$ are called sections of the blow-up $G^{\uparrow n}$.

To simplify notation: given a section $G^{(\alpha)}$ of $G^{\uparrow n}$ and a
subgraph $H\subseteq G$, we write $H^{(\alpha)}$ instead of
$H^{(\alpha_{V(H)})}$ for the corresponding section of $H^{\uparrow n}$.

######  Definition 7.8 (Identifying $\\{0,1\\}^{kn^{2}}$ with the set of
subgraphs of $\mathsf{Path}_{k}^{\uparrow n}$).

  * •

The blow-up $\mathsf{Path}_{k}^{\uparrow n}$ has $kn^{2}$ edges and
$2^{kn^{2}}$ subgraphs. (Recall that graphs have no isolated vertices
according to our definition.)

  * •

For $G\subseteq\mathsf{Path}_{k}$ and $\alpha\in[n]^{V(G)}$, we refer to
graphs $G^{(\alpha)}$ as $G$-sections of $\mathsf{Path}_{k}^{\uparrow n}$.

  * •

We identify elements of $\\{0,1\\}^{kn^{2}}$ with subgraphs of
$\mathsf{Path}_{k}^{\uparrow n}$, as well as $k$-tuples of $n$-by-$n$ Boolean
matrices.

######  Definition 7.9 ($G$-minterms).

For a monotone function $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$, we write
$\mathcal{M}_{G}(f)$ for the $G$-relation

$\displaystyle\mathcal{M}_{G}(f)$
$\displaystyle\vcentcolon=\\{\alpha\in[n]^{V(G)}:G^{(\alpha)}\text{ is a
minterm of }f\\}.$

That is, $\mathcal{M}_{G}(f)$ is the set of $\alpha\in[n]^{V(G)}$ such that
$f(G^{(\alpha)})=1$ and $f(H^{(\alpha)})=0$ for all $H\subsetneqq G$.

For example, we have
$\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{bmm}}_{n,k})=\\{\alpha\in[n]^{\\{0,\dots,k\\}}:\alpha_{0}=\alpha_{k}=1\\}$.
More generally:

######  Observation 7.10.

A monotone function $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$ computes $\textup{{sub-
pmm}}_{n,k}$ (i.e., agrees with $\textup{{bmm}}_{n,k}$ whenever the input is a
$k$-tuple of sub-permutation matrices) if, and only if,
$\mathcal{M}_{\mathsf{Path}_{k}}(f)=\\{\alpha\in[n]^{\\{0,\dots,k\\}}:\alpha_{0}=\alpha_{k}=1\\}$.
In this case, we have $\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f))=n^{-2}$.

The next lemma relates the $G$-minterm relations of $f_{1}\vee f_{2}$ and
$f_{1}\wedge f_{2}$ to those of $f_{1}$ and $f_{2}$.

######  Lemma 7.11.

For every graph $G\subseteq\mathsf{Path}_{k}$ and monotone functions
$f_{1},f_{2}:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$, we have

  * •

$\displaystyle\vphantom{\Big{|}}\mathcal{M}_{G}(f_{1}\vee f_{2})\ \subseteq\
\mathcal{M}_{G}(f_{1})\cup\mathcal{M}_{G}(f_{2})$,

  * •

$\displaystyle\mathcal{M}_{G}(f_{1}\wedge f_{2})\ \subseteq\
\\!\bigcup_{\begin{subarray}{c}\\!\\!G_{1},G_{2}\,\subseteq\,G\,:\\!\\!\\\
\vphantom{\textstyle|}\\!\\!\\!\\!G_{1}\,\cup\,G_{2}\,=\,G\\!\\!\\!\\!\end{subarray}}\\!\\!\\!\mathcal{M}_{G_{1}}(f_{1})\bowtie\mathcal{M}_{G_{2}}(f_{2})\
\subseteq\
\mathcal{M}_{G}(f_{1})\cup\mathcal{M}_{G}(f_{2})\cup\\!\\!\bigcup_{\begin{subarray}{c}\\!\\!G_{1},G_{2}\,\subsetneqq\,G\,:\\!\\!\\\
\vphantom{\textstyle|}\\!\\!\\!\\!G_{1}\,\cup\,G_{2}\,=\,G\\!\\!\\!\\!\end{subarray}}\\!\\!\\!\mathcal{M}_{G_{1}}(f_{1})\bowtie\mathcal{M}_{G_{2}}(f_{2}).$

###### Proof.

These containments follow from the elementary observation: for any monotone
Boolean functions $h_{1}$ and $h_{2}$, every minterm of $h_{1}\vee h_{2}$ is a
minterm of $h_{1}$ or a minterm of $h_{2}$, and every minterm of $h_{1}\wedge
h_{2}$ is the union of a minterm of $h_{1}$ and a minterm of $h_{2}$. ∎

The following corollary extends Lemma 7.11 to $m$-ary disjunctions and
conjunctions. We do not directly use Corollary 7.12 in what follows, but
similar reasoning shows up in the proof of Lemma 7.17.

######  Corollary 7.12 ($m$-ary version of Lemma 7.11).

For every nonempty graph $\emptyset\neq G\subseteq\mathsf{Path}_{k}$, monotone
functions $f_{1},\dots,f_{m}:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$, we have

  * •

$\displaystyle\mathcal{M}_{G}(\bigvee_{j=1}^{m}f_{j})\ \subseteq\
\bigcup_{j=1}^{m}\,\mathcal{M}_{G}(f_{j}),$

  * •

$\displaystyle\mathcal{M}_{G}(\bigwedge_{j=1}^{m}f_{j})\ \subseteq\
\\!\\!\\!\\!\bigcup_{\begin{subarray}{c}\vphantom{\textstyle|}\\!\\!G_{1},\dots,G_{m}\,\subseteq\,G\,:\\!\\!\\\
\vphantom{\textstyle|}\\!\\!G_{1}\,\cup\,\cdots\,\cup\,G_{m}\,=\,G\\!\\!\end{subarray}}\
\operatorname*{\raisebox{-1.5pt}{{$\bowtie$}}\vphantom{\big{|}}}_{j=1}^{m}\
\mathcal{M}_{G_{j}}(f_{j})\ \subseteq\
\bigcup_{t=1}^{\|G\|}\bigcup_{\begin{subarray}{c}\vphantom{\textstyle|}G_{1},\dots,G_{t}\,\subseteq\,G\,:\\\
\vphantom{\textstyle|}G_{1}\,\cup\,\cdots\,\cup\,G_{t}\,=\,G,\\\
\vphantom{\textstyle|}\forall
s\,\in\,[t],\>G_{s}\,\nsubseteq\,G_{1}\,\cup\,\cdots\,\cup\,G_{s-1}\end{subarray}}\bigcup_{\vphantom{\textstyle|}1\,\leq\,j_{1}\,<\,\cdots\,<\,j_{t}\,\leq\,m}\
\,\operatorname*{\raisebox{-1.5pt}{{$\bowtie$}}\vphantom{\big{|}}}_{s=1}^{t}\
\mathcal{M}_{G_{s}}(f_{j_{s}}).$

In the bottom inclusions
$\mathcal{M}_{G}(\bigwedge_{j=1}^{m}f_{j})\subseteq\bigcup\operatorname*{\raisebox{-1.5pt}{{$\bowtie$}}\vphantom{\big{|}}}\ldots\subseteq\bigcup\bigcup\bigcup\operatorname*{\raisebox{-1.5pt}{{$\bowtie$}}\vphantom{\big{|}}}\ldots$,
the lefthand union is indexed over $(2^{\|G\|}-1)^{m}$ ($\leq 2^{km}$)
possibilities for $G_{1},\dots,G_{m}$, while the righthand unions are indexed
over at most $2^{\smash{\|G\|^{2}}}m^{\|G\|}$ ($\leq 2^{\smash{k^{2}}}m^{k}$)
possibilities for $t,j_{1},\dots,j_{t},G_{1},\dots,G_{t}$. In particular, when
$k\leq\log\log n$ and $m\leq n^{1/k}$, there are only
$2^{k^{2}}m^{k}=n^{O(1)}$ indices in the righthand unions. This is essentially
the reason why our $\mathit{SAC^{0}}$ formula lower bounds extend to
$\bigwedge$-fan-in $n^{1/k}$.

###  7.3 Strict join trees

######  Definition 7.13 (Strict join trees).

For $G\subseteq\mathsf{Path}_{k}$, a $G$-join tree $T$ is strict if either
$\|G\|\leq 1$ and $T$ is a single node labeled $G$, or $\|G\|\geq 2$ and
$T=\langle T_{1},T_{2}\rangle$ where $T_{1},T_{2}$ are $G_{1},G_{2}$-join
trees with $G_{1},G_{2}\subsetneqq G$. We denote the set of strict $G$-join
trees by $\mathscr{T}_{G}$.

A simple counting argument shows that $|\mathscr{T}_{G}|\leq 2^{2^{\|G\|}}$.
For bounded $\langle\\!\langle\rangle\\!\rangle$\- or $\llbracket\hskip
0.59998pt\rrbracket{}$-depth, we get an even better bound:

######  Lemma 7.14.

For all $G\subseteq\mathsf{Path}_{k}$, there are at most $2^{\|G\|^{d+1}}$
distinct $T\in\mathscr{T}_{G}$ with $\langle\\!\langle\rangle\\!\rangle$-depth
(or $\llbracket\hskip 0.59998pt\rrbracket$-depth) at most $d$.

###### Proof.

We argue by induction on $d$. Let $\ell\vcentcolon=\|G\|$ and assume $\ell\geq
1$, since otherwise $\mathscr{T}_{G}$ is empty. In the case $d=0$, we have
$|\mathscr{T}_{G}|\leq 1$. In the case $d=1$, we have
$|\mathscr{T}_{G}|=\ell!<2^{\ell^{2}}$.

Suppose $d\geq 2$ and consider any $T=\langle\\!\langle
T_{1},\dots,T_{m}\rangle\\!\rangle\in\mathscr{T}_{G}$ where $m\geq 2$ and each
$T_{j}$ is a $G_{j}$-join tree of $\langle\\!\langle\rangle\\!\rangle$-depth
at most $d-1$. Note that $G_{1}\cup\dots\cup G_{m}=G$ and $G_{j}\nsubseteq
G_{1}\cup\dots\cup G_{j-1}$ for all $j\in[m]$. It follows that $m\leq\ell$,
and there are at most $2^{\ell^{2}}$ possible sequences $(G_{1},\dots,G_{m})$.

For each $j\in[m]$, since $\|G_{j}\|\leq\ell-1$, there are at most
$2^{(\ell-1)^{d}}$ possibilities for $T_{j}$ by the induction hypothesis.
Therefore, the number of possible $T$ is at most

$\displaystyle
2^{\ell^{2}}\cdot(2^{(\ell-1)^{d}})^{\ell}=2^{\ell^{2}+\ell(\ell-1)^{d}}\leq
2^{\ell^{d+1}},$

since $\ell^{2}+\ell(\ell-1)^{d}\leq\ell^{d+1}$ for all $\ell\geq 1$ and
$d\geq 2$.

The exact same argument applies to $\llbracket\hskip
0.59998pt\rrbracket$-depth, since $\llbracket
T_{1},\dots,T_{m}\rrbracket\in\mathscr{T}_{G}$ also implies that
$G_{j}\nsubseteq G_{1}\cup\dots\cup G_{j-1}$ for all $j\in[m]$. ∎

######  Definition 7.15.

Let f be a monotone DeMorgan formula on $kn^{2}$ variables. For each graph
$G\subseteq\mathsf{Path}_{k}$ and strict join tree $T\in\mathscr{T}_{G}$, we
define a subset
$\mathcal{M}_{G}^{(T)}(\textup{{f}})\subseteq\mathcal{M}_{G}(\textup{{f}})$
inductively as follows. If $\|G\|\leq 1$, then
$\mathcal{M}^{(T)}_{G}(\textup{{f}})\vcentcolon=\mathcal{M}_{G}(\textup{{f}})$.
If $\|G\|\geq 2$ and $T=\langle T_{1},T_{2}\rangle$, then

$\displaystyle\mathcal{M}^{(T)}_{G}(\textup{{f}})\vcentcolon=\begin{cases}\emptyset\vphantom{\Big{|}}&\text{if
$\textup{{f}}$ has depth $0$},\\\
\mathcal{M}_{G}(\textup{{f}})\cap\Big{(}\mathcal{M}_{G}^{(T)}(\textup{{f}}_{1})\cup\mathcal{M}_{G}^{(T)}(\textup{{f}}_{2})\Big{)}&\text{if
$\textup{{f}}=\textup{{f}}_{1}\vee\textup{{f}}_{2}$},\vphantom{\bigg{|}}\\\
\mathcal{M}_{G}(\textup{{f}})\cap\Big{(}\mathcal{M}^{(T)}_{G}(\textup{{f}}_{1})\cup\mathcal{M}^{(T)}_{G}(\textup{{f}}_{2})\cup\Big{(}\mathcal{M}^{(T_{1})}_{G_{1}}(\textup{{f}}_{1})\bowtie\mathcal{M}^{(T_{2})}_{G_{2}}(\textup{{f}}_{2})\Big{)}\Big{)}&\text{if
$\textup{{f}}=\textup{{f}}_{1}\wedge\textup{{f}}_{2}$}.\end{cases}$

The next lemma follows directly from Lemma 7.11 and the definition of subsets
$\mathcal{M}_{G}^{(T)}(\textup{{f}})$.

######  Lemma 7.16.

For every monotone DeMorgan formula f on $kn^{2}$ variables and graph
$G\subseteq\mathsf{Path}_{k}$, we have

$\displaystyle\bigcup_{T\in\mathscr{T}_{G}}\mathcal{M}^{(T)}_{G}(\textup{{f}})=\mathcal{M}_{G}(\textup{{f}}).$

Moreover, if f has $\wedge$-left-depth $d$, then
$\mathcal{M}^{(T)}_{G}(\textup{{f}})$ is nonempty only for
$T\in\mathscr{T}_{G}$ with $\langle\\!\langle\rangle\\!\rangle$-depth at most
$d$. It follows that there exists a strict join tree $T\in\mathscr{T}_{G}$
with $\langle\\!\langle\rangle\\!\rangle$-depth at most $d$ such that

$\displaystyle\mu(\mathcal{M}^{(T)}_{G}(\textup{{f}}))\ \geq\
\frac{\mu(\mathcal{M}_{G}(\textup{{f}}))}{|\\{T\in\mathscr{T}_{G}:T\text{ has
$\langle\\!\langle\rangle\\!\rangle$-depth at most $d$}\\}|}\ \geq\
\frac{\mu(\mathcal{M}_{G}(\textup{{f}}))}{2^{\|G\|^{d+1}}}.$

In the event that $\mathcal{M}_{G}(\textup{{f}}_{0})$ is a $G$-pathset for
every graph $G\subseteq\mathsf{Path}_{k}$ and subformula $\textup{{f}}_{0}$ of
f, we are able to bound on the size of f in terms of the pathset complexity of
subsets
$\mathcal{M}^{(T)}_{G}(\textup{{f}})\subseteq\mathcal{M}_{G}(\textup{{f}}_{0})$.

######  Lemma 7.17 (Lemma 6.6 of [23]).

Suppose that f is a monotone DeMorgan formula on $kn^{2}$ variables with
$\wedge$-depth $D$ such that $\mathcal{M}_{G}(\textup{{f}}_{0})$ is a
$G$-pathset for every graph $G\subseteq\mathsf{Path}_{k}$ and subformula
$\textup{{f}}_{0}$ of f. Then for every $G\subseteq\mathsf{Path}_{k}$ and
$T\in\mathscr{T}_{G}$, we have

$\displaystyle\chi_{T}(\mathcal{M}^{(T)}_{G}(\textup{{f}}))\ \leq\
\binom{D+\|G\|-1}{\|G\|-1}\cdot\mathrm{size}(\textup{{f}})\ \leq\
(D+1)^{\|G\|}\cdot\mathrm{size}(\textup{{f}}).$

###### Proof.

We prove the inequality by induction on f. In the base case where f is a
constant, or f is a positive literal and $\|G\|\geq 2$, then
$\mathcal{M}^{(T)}_{G}(\textup{{f}})$ is empty, hence
$\chi_{T}(\mathcal{M}^{(T)}_{G}(\textup{{f}}))=0$ and
$\mathrm{size}(\textup{{f}})=0$. In the remaining base case that f is a
positive literal and $\|G\|=1$, we $\chi_{T}(\cdot)\leq 1$ and
$\mathrm{size}(\textup{{f}})=1$.

The induction step is straightforward when f is a disjunction
$\textup{{f}}_{1}\vee\textup{{f}}_{2}$. We are left with the case that f is a
conjunction $\textup{{f}}_{1}\wedge\textup{{f}}_{2}$. Here the induction step
is trivial when $\|G\|=1$. So we assume that $\|G\|\geq 2$ and $T=\langle
T_{1},T_{2}\rangle$.

For $i\in\\{1,2\\}$, note that $\|G_{i}\|\leq\|G\|-1$ and
$0pt_{\wedge}(\textup{{f}}_{i})\leq D-1$ and
$\mathrm{size}(\textup{{f}})=\mathrm{size}(\textup{{f}}_{1})+\mathrm{size}(\textup{{f}}_{2})$.
By definition of pathset complexity $\chi_{T}(\cdot)$ and the induction
hypothesis applied to $\textup{{f}}_{1}$ and $\textup{{f}}_{2}$,

$\displaystyle\chi_{T}(\mathcal{M}^{(T)}_{G}(\textup{{f}}))$
$\displaystyle=\chi_{T}\Big{(}\mathcal{M}_{G}(\textup{{f}})\cap\Big{(}\mathcal{M}^{(T)}_{G}(\textup{{f}}_{1})\cup\mathcal{M}^{(T)}_{G}(\textup{{f}}_{2})\cup\Big{(}\mathcal{M}^{(T_{1})}_{G_{1}}(\textup{{f}}_{1})\bowtie\mathcal{M}^{(T_{2})}_{G_{2}}(\textup{{f}}_{2})\Big{)}\Big{)}\Big{)}\vphantom{\bigg{|}}$
$\displaystyle\leq\chi_{T}(\mathcal{M}^{(T)}_{G}(\textup{{f}}_{1}))+\chi_{T}(\mathcal{M}^{(T)}_{G}(\textup{{f}}_{2}))+\max\big{\\{}\chi_{T_{1}}(\mathcal{M}^{(T_{1})}_{G_{1}}(\textup{{f}}_{1})),\>\chi_{T_{2}}(\mathcal{M}^{(T_{2})}_{G_{2}}(\textup{{f}}_{2}))\big{\\}}\vphantom{\bigg{|}}$
$\displaystyle\leq\sum_{i\in\\{1,2\\}}\Big{(}\binom{0pt_{\wedge}(\textup{{f}}_{i})+\|G\|-1}{\|G\|-1}+\binom{0pt_{\wedge}(\textup{{f}}_{i})+\|G_{i}\|-1}{\|G_{i}\|-1}\Big{)}\cdot\mathrm{size}(\textup{{f}}_{i})$
$\displaystyle\leq\sum_{i\in\\{1,2\\}}\Big{(}\binom{D+\|G\|-2}{\|G\|-1}+\binom{D+\|G\|-2}{\|G\|-2}\Big{)}\cdot\mathrm{size}(\textup{{f}}_{i})$
$\displaystyle=\binom{D+\|G\|-1}{\|G\|-1}\cdot\mathrm{size}(\textup{{f}}).\qed\vphantom{{}_{\Big{|}}}$

######  Corollary 7.18.

Suppose that f is a monotone DeMorgan formula on $kn^{2}$ variables with
$\wedge$-left-depth $d$ and $\wedge$-depth $D$ such that
$\mathcal{M}_{G}(\textup{{f}}_{0})$ is a $G$-pathset for every graph
$G\subseteq\mathsf{Path}_{k}$ and subformula $\textup{{f}}_{0}$ of f. Then

$\displaystyle\mathrm{size}(\textup{{f}})\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{2^{k^{d+1}}\cdot(D+1)^{k}}\cdot\mu(\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{f}})).$

###### Proof.

By Lemma 7.16, there exists a strict join tree
$T\in\mathscr{T}_{\mathsf{Path}_{k}}$ such that

$\displaystyle\mu(\mathcal{M}^{(T)}_{\mathsf{Path}_{k}}(\textup{{f}}))\geq\frac{1}{2^{k^{d+1}}}\cdot\mu(\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{f}})).$

We now obtain the desired bound as follows:

$\displaystyle\mathrm{size}(\textup{{f}})$
$\displaystyle\geq\frac{1}{(D+1)^{k}}\cdot\chi_{T}(\mathcal{M}^{(T)}_{\mathsf{Path}_{k}}(\textup{{f}}))$
(by Lemma 7.17)
$\displaystyle\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{(D+1)^{k}}\cdot\mu(\mathcal{M}^{(T)}_{\mathsf{Path}_{k}}(\textup{{f}}))$
(by Corollary 6.12(I))
$\displaystyle\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{2^{k^{d+1}}\cdot(D+1)^{k}}\cdot\mu(\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{f}})).$

The hypothesis of Corollary 7.18 requires that $G$-minterm relations
$\mathcal{M}_{G}(\textup{{f}}_{0})$ are pathsets for all subformulas
$\textup{{f}}_{0}$ of f. We point out that this condition may fail to hold
even for relatively simple DeMorgan formulas f. For example, suppose f is the
balanced DeMorgan conversion of the read-once CNF formula
$\bigwedge_{i\in[k]}\ \bigvee_{(a,b)\in[n]^{2}}\ M^{(i)}_{a,b}$. In this case,
$\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{f}})$ is the complete
$\mathsf{Path}_{k}$-relation $[n]^{\\{0,\dots,k\\}}$, which is not a
$\mathsf{Path}_{k}$-pathset since it has density $1$
($>\tilde{n}=\tilde{n}^{\Delta(\mathsf{Path}_{k})}$).

###  7.4 Random restriction lemma

In order to make use of Corollary 7.18, we require a result (Lemma 7.24)
showing that whenever a monotone function $f:\\{0,1\\}^{kn}\to\\{0,1\\}$ is
computable by a reasonably small $\mathit{AC^{0}}$ formula of reasonably
bounded depth, the $G$-minterm relation of a certain random restriction of $f$
is a $G$-pathset with very high probability.

######  Definition 7.19 (Random matrices
$\bm{\xi}\leq\bm{\zeta}\in\\{0,1\\}^{n\times n}$ and graphs
${\bm{\Xi}}\subseteq\mathsf{Path}_{k}^{\uparrow n}$).

  * •

Let $\bm{\zeta}\in\\{0,1\\}^{n\times n}$ be a random Boolean matrix with
i.i.d. $\mathrm{Bernoulli}(n^{-1-\frac{1}{2k}})$ entries.

  * •

Let $\bm{\xi}\in\\{0,1\\}^{n\times n}$ be the sub-permutation matrix induced
by $\bm{\zeta}$ as follows:

$\displaystyle\bm{\xi}_{a,b}$
$\displaystyle\vcentcolon=\begin{cases}1&\text{if }\bm{\zeta}_{a,b}=1\text{
and }\bm{\zeta}_{a^{\prime},b}=\bm{\zeta}_{a,b^{\prime}}=0\text{ for all
}a^{\prime}\neq a\text{ and }b^{\prime}\neq b,\\\
0&\text{otherwise.}\end{cases}\qquad$

  * •

Let $\bm{\zeta}^{(1)},\dots,\bm{\zeta}^{(k)}\in\\{0,1\\}^{n\times n}$ be
independent random matrices with distribution $\bm{\zeta}$, let
$\bm{\xi}^{(1)},\dots,\bm{\zeta}^{(k)}\in\\{0,1\\}^{n\times n}$ be the induced
sub-permutation matrices, and let
${\bm{\Xi}}\vcentcolon=(\bm{\xi}^{(1)},\dots,\bm{\zeta}^{(k)})$ which we
regard as an element of $\\{0,1\\}^{kn^{2}}$ as well as a subgraph
${\bm{\Xi}}\subseteq\mathsf{Path}_{k}^{\uparrow n}$.

######  Definition 7.20 (The restricted function $f^{\cup{\bm{\Xi}}}$).

  * •

For a Boolean function $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$, let
$f^{\cup{\bm{\Xi}}}:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$ denote the random function
defined by $f^{\cup{\bm{\Xi}}}(X)\vcentcolon=f(X\cup{\bm{\Xi}})$ for all
$X\subseteq\mathsf{Path}_{k}^{\uparrow n}$. (Note that if $f$ is monotone,
then so is $f^{\cup{\bm{\Xi}}}$.)

  * •

For a $kn^{2}$-variable DeMorgan formula f, let
$\textup{{f}}^{\cup{\bm{\Xi}}}$ denote the formula obtained from f by
substituting the constant $1$ (resp. $0$) at each positive (resp. negative)
literal corresponding to an edge of ${\bm{\Xi}}$. (Note that if f computes
$f$, then $\textup{{f}}^{\cup{\bm{\Xi}}}$ computes $f^{\cup{\bm{\Xi}}}$.)

The next lemma extends Observation 7.10 concerning the
$\mathsf{Path}_{k}$-minterms of monotone functions that compute $\textup{{sub-
pmm}}_{n,k}$.

######  Lemma 7.21.

If $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$ is a monotone function which agrees with
$\textup{{sub-pmm}}_{n,k}$ on every $k$-tuple of sub-permutation matrices,
then

$\displaystyle\operatorname*{\mathds{P}}\Big{[}\
\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f^{\cup{\bm{\Xi}}}))\geq\frac{1}{2n^{2}}\
\Big{]}=1-o(1).$

###### Proof.

Let $\bm{\zeta}^{(1)},\dots,\bm{\zeta}^{(k)}\in\\{0,1\\}^{n\times n}$ be the
random matrices which generate the
$\bm{\xi}^{(1)},\dots,\bm{\xi}^{(k)}\in\\{0,1\\}^{n\times n}$ comprising
${\bm{\Xi}}$. As noted in Observation 7.10, we have
$\mathcal{M}_{\mathsf{Path}_{k}}(f)=\\{\alpha\in[n]^{\\{0,\dots,k\\}}:\alpha_{0}=\alpha_{k}=1\\}$.
For each $\alpha$ in this set, a sufficient condition for
$\alpha\in\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f^{\cup{\bm{\Xi}}}))$ is that
$\bm{\zeta}^{(i)}_{\smash{a,\alpha_{i}}}=\bm{\zeta}^{(i)}_{\smash{\alpha_{i-1},b}}=0$
for all $a,b\in[n]$. (In this case, ${\bm{\Xi}}\cup G^{(\alpha)}$ is a
$k$-tuple of sub-permutation matrices for every $G\subseteq\mathsf{Path}_{k}$,
from which it follows that
$\alpha\in\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f^{\cup{\bm{\Xi}}}))$.) This
sufficient condition occurs with probability
$(1-n^{-1-\frac{1}{2k}})^{k(2n-1)}=1-O(kn^{-\frac{1}{2k}})=1-o(1)$. Therefore,
by linearity of expectation,

$\displaystyle\operatorname*{\mathds{E}}\big{[}\
\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f^{\cup{\bm{\Xi}}}))\
\big{]}\geq(1-o(1))\cdot\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f))=(1-o(1))\cdot\frac{1}{n^{2}}.$

A straightforward application of Janson’s inequality [14] shows that
$\mu(\mathcal{M}_{\mathsf{Path}_{k}}(f^{\cup{\bm{\Xi}}}))$ is at least half
its expectation with very high probability. ∎

The next definition gives a version of the relation $\mathcal{M}_{G}(f)$ for
non-monotone functions $f$.

######  Definition 7.22 (The relation $\mathcal{N}_{G}(f)$).

  * •

For a (not necessarily monotone) function $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$
and a graph $G\subseteq\mathsf{Path}_{k}$ and $\alpha\in[n]^{V(G)}$, let
$f{\upharpoonright}G^{(\alpha)}:\\{0,1\\}^{\|G\|}\to\\{0,1\\}$ denote
restricted subfunction
$f{\upharpoonright}G^{(\alpha)}(H)\vcentcolon=H^{(\alpha)}$ where we identify
each input $H\in\\{0,1\\}^{\|G\|}$ with the corresponding subgraph of $G$.

  * •

The relation $\mathcal{N}_{G}(f)\subseteq[n]^{V(G)}$ by

$\displaystyle\mathcal{N}_{G}(f)$
$\displaystyle\vcentcolon=\\{\alpha\in[n]^{V(G)}:f{\upharpoonright}G^{(\alpha)}\text{
depends on all $\|G\|$ coordinates}\\}.$

For monotone functions $f$, note that
$\mathcal{M}_{G}(f)\subseteq\mathcal{N}_{G}(f)$ (hence if $\mathcal{N}_{G}(f)$
is a $G$-pathset, then so is $\mathcal{M}_{G}(f)$).

Since it will be useful later, we state here a variant of Lemma 7.17 with
$\mathcal{N}_{G}(\cdot)$ in place of $\mathcal{M}_{G}(\cdot)$. (The proof is
identical.)

######  Lemma 7.23.

Suppose that f is a DeMorgan formula on $kn^{2}$ variables with depth $D$ such
that $\mathcal{N}_{G}(\textup{{f}}_{0})$ is a $G$-pathset for every graph
$G\subseteq\mathsf{Path}_{k}$ and subformula $\textup{{f}}_{0}$ of f. Then for
every $G\subseteq\mathsf{Path}_{k}$ and $T\in\mathscr{T}_{G}$, we have

$\displaystyle\chi_{T}(\mathcal{N}^{(T)}_{G}(\textup{{f}}))$
$\displaystyle\leq(D+1)^{\|G\|}\cdot\mathrm{size}(\textup{{f}}).$

We conclude this subsection by stating a key lemma from [23], which implies
that relations $\mathcal{M}_{G}(f^{\cup{\bm{\Xi}}})$ are likely to be
$G$-pathsets whenever $f$ is computable by monotone $\mathit{AC^{0}}$ formulas
of reasonable size and depth.

######  Lemma 7.24 (Lemma 6.5 of [23]).

Suppose that $f:\\{0,1\\}^{kn^{2}}\to\\{0,1\\}$ is computable by a (not
necessarily monotone) $\mathit{AC^{0}}$ formula of size at most $n^{k}$ and
depth at most $\frac{\log n}{(\log\log n)^{6}}$. Then for every
$G\subseteq\mathsf{Path}_{k}$, we have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathcal{N}_{G}(f^{\cup{\bm{\Xi}}})\text{ is \text@underline{not} a
$G$-pathset}\ \big{]}$ $\displaystyle\leq O(n^{-2k}).$

###  7.5 Tradeoff (I)+ for monotone $\mathit{SAC^{0}}$ formulas

We are ready to prove our size-depth tradeoff for monotone $\mathit{SAC^{0}}$
formulas.

######  Theorem 7.25 (Tradeoff (I)+ of Theorem 1.6).

Suppose that F is a monotone $\mathit{SAC^{0}}$ formula of $\bigwedge$-depth
$d$ and $\bigwedge$-fan-in $n^{1/k}$ which computes $\textup{{sub-pmm}}_{n,k}$
where $k\leq\log\log n$ and $d\leq\log k$. Then F has size
$n^{\Omega(dk^{1/d})}$.

###### Proof.

Without loss of generality, assume that F has size at most $n^{k}$, since this
is greater than the lower bound we wish to show. Let f be the right-deep
DeMorgan conversion of F. Note that even though f has very large depth, it has
$\wedge$-left-depth $d$ and $\wedge$-depth at most $dn^{1/k}$. Moreover, each
subformula $\textup{{f}}_{0}$ of f is equivalent to a monotone
$\mathit{AC^{0}}$ formula of $\bigwedge$-depth at most $d$ (and depth at most
$2d+1=O(\log\log n)$) and size at most $n^{k}$. In particular,
$\textup{{f}}_{0}$ satisfies the hypothesis of Lemma 7.24.

We now observe that each of the following statements hold with probability
$1-o(1)$:

  * •

$\mathcal{M}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})$ is a $G$-pathset for
every subformula $\textup{{f}}_{0}$ of f and $G\subseteq\mathsf{Path}_{k}$

(by Lemma 7.24 and a union bound over at most $O(n)^{k}$ choices of
$\textup{{f}}_{0}$ and $G$),

  * •

$\displaystyle\mathrm{size}(\textup{{f}}^{\cup{\bm{\Xi}}})\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{2^{k^{d+1}}\cdot(dn^{1/k}+1)^{k}}\cdot\mu(\mathcal{M}_{\mathsf{Path}_{k}}(\textup{{f}}^{\cup{\bm{\Xi}}}))$
(by Corollary 7.18),

  * •

$\displaystyle\mathrm{size}(\textup{{f}}^{\cup{\bm{\Xi}}})\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{2^{k^{d+1}}\cdot(dn^{1/k}+1)^{k}\cdot
2n^{2}}$ (by Lemma 7.21).

Since
$\mathrm{size}(\textup{{F}})=\mathrm{size}(\textup{{f}})\geq\mathrm{size}(\textup{{f}}^{\cup{\bm{\Xi}}})$,
it follows that

$\displaystyle\mathrm{size}(\textup{{F}})$
$\displaystyle\geq\frac{n^{\Omega(d(k^{1/d}-1))}}{2^{k^{d+1}}\cdot(dn^{1/k}+1)^{k}\cdot
2n^{2}}.$

Since $k\leq\log\log n$ and $d\leq\log k$, we have $2^{k^{d+1}}\leq n^{o(1)}$
and $(dn^{1/k}+1)^{k}=n^{1+o(1)}$, so the denominator above is $n^{O(1)}$,
whereas the numerator is at least $n^{\Omega(\log k)}$. We conclude that F has
size $n^{\Omega(d(k^{1/d}-1))}$ as required. ∎

Our proof of tradeoff (I)+ shows that we can slightly extend the range of $k$
from $\log\log n$ to $2^{\sqrt{\log\log n}}$ and $\bigwedge$-fan-in from
$n^{1/k}$ to $n^{(\log k)/k}$. While the range of $k$ can probably be pushed
further, the proof breaks down for larger $\bigwedge$-fan-in
$D=n^{\omega((\log k)/k)}$; this is ultimately due to the $D^{k}$ factor in
the bound of Lemma 7.17. Also notice that our $n^{\Omega(dk^{1/d})}$ lower
bound for monotone $\mathit{SAC^{0}}$ formulas of $\bigwedge$-depth $d$ cannot
possibly extend to unbounded fan-in $\mathit{AC^{0}}$ formulas of
$\bigwedge$-depth $d$, in light of the $n^{O(dk^{1/(2d+1)})}$ upper bound
given by the monotone $\Sigma_{2d+1}$ formulas of Proposition 1.3(II).

###  7.6 Strict support tree of a $k$-variable DeMorgan formula

We next define notions of strictness and $\llbracket\hskip
0.59998pt\rrbracket{}$-depth for DeMorgan formulas, which are analogous to the
corresponding notions for join trees. Even though we only apply these notions
to $k$-variable DeMorgan formulas, we state the definitions more generally
without reference to $k$.

######  Definition 7.26 (Strict DeMorgan formulas and operations
$\textup{{strict}}(\textup{{g}})$ and $\mathit{strict}(T)$).

  * •

A DeMorgan formula g is strict if either

    * –

it has depth $0$ (i.e., g is a constant or literal), or

    * –

it is $\textup{{g}}_{1}\wedge\textup{{g}}_{2}$ or
$\textup{{g}}_{1}\wedge\textup{{g}}_{2}$ where
$\textup{{g}}_{1},\textup{{g}}_{2}$ are strict and compute distinct functions
from g (i.e., $\textup{{g}}_{1}\not\equiv\textup{{g}}$ and
$\textup{{g}}_{2}\not\equiv\textup{{g}}$).

  * •

For every DeMorgan formula g, we define an equivalent strict DeMorgan formula
$\textup{{strict}}(\textup{{g}})$ inductively as follows:

    * –

if g has depth $0$, then
$\textup{{strict}}(\textup{{g}})\vcentcolon=\textup{{g}}$,

    * –

if g is $\textup{{g}}_{1}\wedge\textup{{g}}_{2}$ (resp.
$\textup{{g}}_{1}\vee\textup{{g}}_{2}$), then

$\displaystyle\textup{{strict}}(\textup{{g}})\vcentcolon=\begin{cases}\textup{{strict}}(\textup{{g}}_{1})&\text{if
}\textup{{g}}_{1}\equiv\textup{{g}},\\\
\textup{{strict}}(\textup{{g}}_{2})&\text{if
}\textup{{g}}_{1}\not\equiv\textup{{g}}\text{ and
}\textup{{g}}_{2}\equiv\textup{{g}},\\\
\textup{{strict}}(\textup{{g}}_{1})\wedge\textup{{strict}}(\textup{{g}}_{2})\text{
(resp.\
$\textup{{strict}}(\textup{{g}}_{1})\vee\textup{{strict}}(\textup{{g}}_{2})$)}&\text{otherwise.}\end{cases}$

(Note that g is strict if, and only if,
$\textup{{g}}=\textup{{strict}}(\textup{{g}})$. On the other hand,
$\textup{{g}}\equiv\textup{{strict}}(\textup{{g}})$ for all g.)

  * •

For every $G$-join tree $T$, we define a strict $G$-join tree
$\mathit{strict}(T)$ in a similar fashion:

    * –

if $T$ has $\langle\hskip 0.59998pt\rangle$-depth $0$, then
$\mathit{strict}(T)\vcentcolon=T$,

    * –

if $T=\langle T_{1},T_{2}\rangle$ where $T_{1},T_{2}$ are $G_{1},G_{2}$-join
trees, then

$\displaystyle\mathit{strict}(T)\vcentcolon=\begin{cases}\mathit{strict}(T_{1})&\text{if
}G_{1}=G,\\\ \mathit{strict}(T_{2})&\text{if }G_{1}\neq G\text{ and
}G_{2}=G,\\\
\langle\mathit{strict}(T_{1}),\mathit{strict}(T_{2})\rangle&\text{otherwise.}\end{cases}$

To help the reader keep track of the types of objects, we use typewriter font
for the strict operator on DeMorgan formulas and italics for the
$\mathit{strict}$ operator on join trees. (Later on in Definition 7.29, we use
sans-serif $\mathsf{Supp}(\textup{{g}})$ for a subgraph of $\mathsf{Path}_{k}$
and italic $S(\textup{{g}})$ for a join tree associated with g.)

######  Definition 7.27 ($\llbracket\hskip 0.59998pt\rrbracket$-depth of
DeMorgan formulas).

  * •

For any DeMorgan formulas $\textup{{g}}_{1},\dots,\textup{{g}}_{m}$, we define
DeMorgan formulas
$\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\wedge}$ and
$\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\vee}$
inductively by

$\displaystyle\llbracket\textup{{g}}_{1}\rrbracket_{\wedge}=\llbracket\textup{{g}}_{1}\rrbracket_{\vee}$
$\displaystyle\vcentcolon=\textup{{g}}_{1},$ $\displaystyle\text{for
}m=1,\vphantom{\big{|}}$
$\displaystyle\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\wedge}$
$\displaystyle\vcentcolon=\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m-1}\rrbracket_{\wedge}\wedge\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m-2},\textup{{g}}_{m}\rrbracket_{\wedge}$
$\displaystyle\text{for }m\geq 2,\vphantom{\big{|}}$
$\displaystyle\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\vee}$
$\displaystyle\vcentcolon=\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m-1}\rrbracket_{\vee}\vee\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m-2},\textup{{g}}_{m}\rrbracket_{\vee}$
$\displaystyle\text{for }m\geq 2.\vphantom{\big{|}}$

  * •

The $\llbracket\hskip 0.59998pt\rrbracket{}$-depth of a DeMorgan formula g is
defined inductively as follows:

    * –

if g has depth $0$, then $0pt_{\llbracket\hskip
0.41998pt\rrbracket{}}(\textup{{g}})\vcentcolon=0$,

    * –

if g has depth $\geq 1$, then

$\displaystyle 0pt_{\llbracket\hskip
0.41998pt\rrbracket{}}(\textup{{g}})\vcentcolon=1+\min_{\begin{subarray}{c}m\,\geq\,2,\
\textup{{g}}_{1},\dots,\textup{{g}}_{m}\,:\\\
\textup{{g}}\,=\,\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\wedge}\text{
or
}\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\vee}\end{subarray}}\max_{i\in[m]}\
0pt_{\llbracket\hskip 0.41998pt\rrbracket{}}(\textup{{g}}_{i}).$

We now restrict attention to $k$-variable DeMorgan formulas, whose variables
we identify with edges of $\mathsf{Path}_{k}$ and whose inputs in
$\\{0,1\\}^{k}$ we identify with subgraphs of $\mathsf{Path}_{k}$.

######  Lemma 7.28.

There are at most $2^{2^{(d+1)(k+1)}}$ distinct strict $k$-variable DeMorgan
formulas of $\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$.

###### Proof.

Consider any strict $k$-variable DeMorgan formula g of $\llbracket\hskip
0.59998pt\rrbracket{}$-depth $d$. Without loss of generality,

$\displaystyle\textup{{g}}=\llbracket\textup{{g}}_{1},\dots,\textup{{g}}_{m}\rrbracket_{\wedge}$

for some $\textup{{g}}_{1},\dots,\textup{{g}}_{m}$ of $\llbracket\hskip
0.59998pt\rrbracket{}$-depth at most $d-1$. Note that
$\textup{{g}}_{1},\dots,\textup{{g}}_{m}$ are necessarily also strict.

Let $g_{1},\dots,g_{m}:\\{0,1\\}^{k}\to\\{0,1\\}$ be the functions computes by
$\textup{{g}}_{1},\dots,\textup{{g}}_{m}$. Strictness of g implies that

$\displaystyle g_{1},\quad g_{1}\wedge g_{2},\quad g_{1}\wedge g_{2}\wedge
g_{3},\quad\dots,\quad g_{1}\wedge\dots\wedge g_{m}$

is a strictly decreasing sequence of Boolean functions. Moreover,
$g_{1}\wedge\dots\wedge g_{m}\not\equiv 0$ assuming $m\geq 1$. It follows that
$m\leq 2^{k}$. (Whereas there are $2^{2^{k}}$ distinct Boolean functions
$\\{0,1\\}^{k}\to\\{0,1\\}$, the longest decreasing sequence of non-zero
functions has length $2^{k}$.)

We conclude that

$\big{|}\big{\\{}\textup{strict $k$-variable DeMorgan formulas of
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$}\big{\\}}\big{|}\\\
\leq 2+2k+2\big{|}\big{\\{}\textup{strict $k$-variable DeMorgan formulas of
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most
$d-1$}\big{\\}}\big{|}\vphantom{\big{|}}^{2^{k}}.$

(Here the additive $2+2k$ counts the depth-$0$ formulas, and the other factor
$2$ arises from the choice of top gate type.) The bound of the lemma follows
since $2+2k+2^{2^{d(k+1)}}\leq 2^{2^{(d+1)(k+1)}}$ for all $d,k\geq 0$. ∎

The next definition associates a join tree $S(\textup{{g}})$ with each
$k$-variable DeMorgan formula g.

######  Definition 7.29 (Support, restriction, and support tree).

  * •

The support of a Boolean function $g:\\{0,1\\}^{k}\to\\{0,1\\}$ is the set
$\mathsf{Supp}(g)\subseteq[k]$ of coordinates on which $g$ depends, that is,

$\displaystyle\mathsf{Supp}(g)$ $\displaystyle\vcentcolon=\\{i\in[k]:\exists
y\in\\{0,1\\}^{k},\ g(y)\neq
g(y_{1},\dots,y_{i-1},1-y_{i},y_{i+1},\dots,y_{k})\\}.$

(We identify $\mathsf{Supp}(g)$ with the corresponding subgraph of
$\mathsf{Path}_{k}$.)

The support of a $k$-variable DeMorgan formula g, denoted
$\mathsf{Supp}(\textup{{g}})$, is the support of the Boolean function it
computes.

  * •

For a $k$-variable DeMorgan formula g and a subgraph
$H\subseteq\mathsf{Path}_{k}$, let $\textup{{g}}{\upharpoonright}H$ denote the
DeMorgan formula obtained from g by syntactically relabeling to $0$ (resp.
$1$) each leaf labeled by a positive (resp. negative) literal whose coordinate
lies in $E(\mathsf{Path}_{k})\setminus E(H)$.

(Observe that $\mathsf{Supp}(\textup{{g}}{\upharpoonright}H)\subseteq H$ and
$\textup{{g}}\equiv\textup{{g}}{\upharpoonright}\mathsf{Supp}(\textup{{g}})$,
even though g and $\textup{{g}}{\upharpoonright}\mathsf{Supp}(\textup{{g}})$
are not necessarily equal.)

  * •

For every $k$-variable DeMorgan formula g, we define a join tree
$S(\textup{{g}})$, called the support tree of g, inductively as follows:

    * –

if g is a constant (i.e., $0$ or $1$), then $S(\textup{{g}})$ is the empty
join tree;

    * –

if g is the $i$th positive or negative literal, then $S(\textup{{g}})$ is the
single-node join tree labeled by $E_{i}$ (i.e., the $i$th single-edge subgraph
of $\mathsf{Path}_{k}$);

    * –

if g is $\textup{{g}}_{1}\wedge\textup{{g}}_{2}$ or
$\textup{{g}}_{1}\vee\textup{{g}}_{2}$, then
$S(\textup{{g}})\vcentcolon=S(\textup{{g}}_{1}{\upharpoonright}\mathsf{Supp}(\textup{{g}}))\cup
S(\textup{{g}}_{2}{\upharpoonright}\mathsf{Supp}(\textup{{g}})).$

Note that $S(\textup{{g}})$ is a $\mathsf{Supp}(\textup{{g}})$-join tree. (Had
we instead defined $S(\textup{{g}})\vcentcolon=S(\textup{{g}}_{1})\cup
S(\textup{{g}}_{2})$, then $S(\textup{{g}})$ would be a $G$-join tree where
$G$ is the supergraph of $\mathsf{Supp}(\textup{{g}})$ that contain the edges
of $\mathsf{Path}_{k}$ corresponding to all literals that appear in g.)

  * •

We refer to $\mathit{strict}(S(\textup{{g}}))$ as the strict support tree of
g. Note that $\mathit{strict}(S(\textup{{g}}))$ is a strict
$\mathsf{Supp}(\textup{{g}})$-join tree (i.e., an element of
$\mathscr{T}_{\mathsf{Supp}(\textup{{g}})}$).

The next lemma follows directly from definitions.

######  Lemma 7.30.

For every $k$-variable DeMorgan formula g, the $\llbracket\hskip
0.59998pt\rrbracket{}$-depth of the join tree $S(\textup{{g}})$ (and hence
also $\mathit{strict}(S(\textup{{g}}))$) is at most the $\llbracket\hskip
0.59998pt\rrbracket{}$-depth of g.∎

###  7.7 The distribution of
$\textup{{strict}}(\mathscr{D}_{t}(\textup{{G}}))$ for a $k$-variable
$\mathit{AC^{0}}$ formula G

In this subsection, we prove a key result (Lemma 7.33) on the distribution of
$\textup{{strict}}(\textup{{g}})$ for the randomized balanced DeMorgan
conversion $\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})$ (Def. 7.4) of a
$k$-variable $\mathit{AC^{0}}$ formula G. We begin with a preliminary lemma on
the distribution of $\mathit{strict}(\bm{T}_{t})$ for a certain family of
random join trees $\bm{T}_{t}$.

######  Lemma 7.31.

Fix any real numbers $p_{1}\geq\dots\geq p_{k}>0$ with $p_{1}+\dots+p_{k}=1$.
For each $t\in\mathbb{N}$, let $\bm{T}_{t}$ be a random join tree of
$\langle\hskip 0.59998pt\rangle$-depth $t$ with $2^{t}$ leaves independently
labeled by single-edge graphs $E_{1},\dots,E_{k}$ with probability
$p_{1},\dots,p_{k}$ respectively. Then for all $t\geq\log(\frac{1}{p_{k}})+k$,
we have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{t})=\llbracket E_{1},\dots,E_{k}\rrbracket\
\big{]}\geq\exp(-O(2^{k})).$

A key point in Lemma 7.31 is that the bound $\exp(-O(2^{k}))$ is independent
of $t$ and the distribution $p_{1},\dots,p_{k}$).

###### Proof.

First, consider the case of the uniform distribution
$p_{1}=\dots=p_{k}=\frac{1}{k}$. Here we have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{k})=\llbracket E_{1},\dots,E_{k}\rrbracket\
\big{]}=\operatorname*{\mathds{P}}\big{[}\ \bm{T}_{k}=\llbracket
E_{1},\dots,E_{k}\rrbracket\ \big{]}=k^{-k}.$

Note that for any $t\geq k$, we have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{t})=\llbracket E_{1},\dots,E_{k}\rrbracket\
\big{]}\geq\operatorname*{\mathds{P}}\big{[}\ \text{the leftmost depth-$k$
sub-join tree of $\bm{T}_{t}$ equals }\llbracket E_{1},\dots,E_{k}\rrbracket\
\big{]}=k^{-k}.$

To illustrate the general argument, consider the following (essentially
geometric) distribution with $k=4$:

$\displaystyle p_{1}\approx 0.99,\qquad p_{2}=2^{-10},\qquad
p_{3}=2^{-100},\qquad p_{4}=2^{-1000}.$

First, note that

$\displaystyle\operatorname*{\mathds{P}}\big{[}\ \bm{T}_{1000}\text{ contains
a single }E_{4}\ \big{]}=\operatorname*{\mathds{P}}\big{[}\
\mathrm{Binomial}(2^{1000},2^{-1000})=1\
\big{]}\approx\frac{1}{\mathrm{e}{}}.$

Letting $\bm{T}_{999}^{(\mathrm{L})}$ and $\bm{T}_{999}^{(\mathrm{R})}$ be the
left and right children of the root of $\bm{T}_{1000}$, we next observe that

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\underbrace{\bm{T}_{999}^{(\mathrm{L})}\text{ contains no }E_{4}\text{ and
}\bm{T}_{999}^{(\mathrm{R})}\text{ contains a single
}E_{4}}_{\textstyle\textup{call this event }\mathcal{E}}\
\big{]}\approx\frac{1}{\mathrm{e}{}^{2}}.$

Conditioned on event $\mathcal{E}$, let $\bm{T}_{100}^{(\mathrm{L})}$ be the
leftmost depth-$k$ sub-join tree of $\bm{T}_{999}^{(\mathrm{L})}$, and let
$\bm{T}_{100}^{(\mathrm{R})}$ be the unique depth-$k$ sub-join tree of
$\bm{T}_{999}^{(\mathrm{R})}$ that contains $E_{4}$. Now observe that a
sufficient condition for $\mathit{strict}(\bm{T}_{1000})=\llbracket
E_{1},E_{2},E_{3},E_{4}\rrbracket$ is that

  1. (a)

event $\mathcal{E}$ holds,

  2. (b)

$\mathit{strict}(\bm{T}_{100}^{(\mathrm{L})})=\llbracket
E_{1},E_{2},E_{3}\rrbracket$, and

  3. (c)

$\mathit{strict}(\bm{T}_{100}^{(\mathrm{R})})=\llbracket
E_{1},E_{2},E_{4}\rrbracket$.

(Given $\mathcal{E}$, condition (b) implies that
$\mathit{strict}(\bm{T}_{999}^{(\mathrm{L})})=\llbracket
E_{1},E_{2},E_{3}\rrbracket$ and (c) implies that
$\mathit{strict}(\bm{T}_{999}^{(\mathrm{R})})=\llbracket
E_{1},E_{2},E_{4}\rrbracket$. Conditions (a),(b),(c) therefore together imply
that $\mathit{strict}(\bm{T}_{1000})=\llbracket
E_{1},E_{2},E_{3},E_{4}\rrbracket$.) We now have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{1000})={}$ $\displaystyle\llbracket
E_{1},E_{2},E_{3},E_{4}\rrbracket\ \big{]}$
$\displaystyle\geq\operatorname*{\mathds{P}}\Big{[}\ \mathcal{E}\text{ and
}\mathit{strict}(\bm{T}_{100}^{(\mathrm{L})})=\llbracket
E_{1},E_{2},E_{3}\rrbracket\text{ and
}\mathit{strict}(\bm{T}_{100}^{(\mathrm{R})})=\llbracket
E_{1},E_{2},E_{4}\rrbracket\ \Big{]}$
$\displaystyle\approx\frac{1}{\mathrm{e}{}^{2}}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{100}^{(\mathrm{L})})=\llbracket
E_{1},E_{2},E_{3}\rrbracket\ \Big{|}\ \mathcal{E}\
\Big{]}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{100}^{(\mathrm{R})})=\llbracket
E_{1},E_{2},E_{4}\rrbracket\ \Big{|}\ \mathcal{E}\ \Big{]}.$

Splitting $\bm{T}_{100}^{(\mathrm{L})}$ (resp. $\bm{T}_{100}^{(\mathrm{R})}$)
into left and right subtrees $\bm{T}_{99}^{(\mathrm{L}\mathrm{L})}$ and
$\bm{T}_{99}^{(\mathrm{L}\mathrm{R})}$ (resp.
$\bm{T}_{99}^{(\mathrm{R}\mathrm{L})}$ and
$\bm{T}_{99}^{(\mathrm{R}\mathrm{R})}$), we continue this analysis:

$\displaystyle\operatorname*{\mathds{P}}\Big{[}\
\underbrace{\bm{T}_{99}^{(\mathrm{L}\mathrm{L})}\text{ contains no
}E_{3}\text{ and }\bm{T}_{99}^{(\mathrm{L}\mathrm{R})}\text{ contains a single
}E_{3}}_{\textstyle\textup{call this event }\mathcal{E}^{(\mathrm{L})}}\
\Big{|}\ \mathcal{E}\ \Big{]}$
$\displaystyle\approx\frac{1}{\mathrm{e}{}^{2}},$
$\displaystyle\operatorname*{\mathds{P}}\Big{[}\
\underbrace{\bm{T}_{99}^{(\mathrm{R}\mathrm{L})}\text{ contains no
}E_{4}\text{ and }\bm{T}_{99}^{(\mathrm{R}\mathrm{R})}\text{ contains a single
}E_{4}}_{\textstyle\textup{call this event }\mathcal{E}^{(\mathrm{R})}}\
\Big{|}\ \mathcal{E}\ \Big{]}$
$\displaystyle\approx\frac{1}{\mathrm{e}{}^{2}}.$

Next, for appropriate definitions of sub-join trees
$\bm{T}_{10}^{(\mathrm{L}\mathrm{L})},\bm{T}_{10}^{(\mathrm{L}\mathrm{R})}$ of
$\bm{T}_{99}^{(\mathrm{L})}$ and
$\bm{T}_{10}^{(\mathrm{R}\mathrm{L})},\bm{T}_{10}^{(\mathrm{R}\mathrm{R})}$ of
$\bm{T}_{99}^{(\mathrm{R})}$, we have

$\displaystyle\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{100}^{(\mathrm{L})})={}$ $\displaystyle\llbracket
E_{1},E_{2},E_{3}\rrbracket\ \Big{|}\ \mathcal{E}\ \Big{]}$
$\displaystyle\approx\frac{1}{\mathrm{e}{}^{2}}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{10}^{(\mathrm{L}\mathrm{L})})=\llbracket
E_{1},E_{2}\rrbracket\ \Big{|}\ \mathcal{E}\wedge\mathcal{E}^{(\mathrm{L})}\
\Big{]}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{10}^{(\mathrm{L}\mathrm{R})})=\llbracket
E_{1},E_{3}\rrbracket\ \Big{|}\ \mathcal{E}\wedge\mathcal{E}^{(\mathrm{L})}\
\Big{]},$ $\displaystyle\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{100}^{(\mathrm{R})})={}$ $\displaystyle\llbracket
E_{1},E_{2},E_{4}\rrbracket\ \Big{|}\ \mathcal{E}\ \Big{]}$
$\displaystyle\approx\frac{1}{\mathrm{e}{}^{2}}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{10}^{(\mathrm{R}\mathrm{L})})=\llbracket
E_{1},E_{2}\rrbracket\ \Big{|}\ \mathcal{E}\wedge\mathcal{E}^{(\mathrm{R})}\
\Big{]}\cdot\operatorname*{\mathds{P}}\Big{[}\
\mathit{strict}(\bm{T}_{10}^{(\mathrm{R}\mathrm{R})})=\llbracket
E_{1},E_{4}\rrbracket\ \Big{|}\ \mathcal{E}\wedge\mathcal{E}^{(\mathrm{R})}\
\Big{]}.$

This analysis continues down one more layer. In the end we get a bound

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{1000})=\llbracket E_{1},E_{2},E_{3},E_{4}\rrbracket\
\big{]}$
$\displaystyle\gtrsim\frac{1}{\mathrm{e}{}^{2}}\left(\frac{1}{\mathrm{e}{}^{2}}\left(\frac{1}{\mathrm{e}{}^{2}}\right)\left(\frac{1}{\mathrm{e}{}^{2}}\right)\right)\left(\frac{1}{\mathrm{e}{}^{2}}\left(\frac{1}{\mathrm{e}{}^{2}}\right)\left(\frac{1}{\mathrm{e}{}^{2}}\right)\right)=\frac{1}{\mathrm{e}{}^{14}}.$

Generalizing this example to larger $k$, we get a lower bound

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\mathit{strict}(\bm{T}_{10^{k}})=\llbracket E_{1},\dots,E_{k}\rrbracket\
\big{]}$ $\displaystyle\gtrsim\exp(-2(2^{k}-1)),$

which is essentially the worst case for the lemma.

To generalize this argument for an arbitrary distribution $p_{1}\geq\dots\geq
p_{k}>0$, in place of depths $1,10,100,1000$ in the example above, we consider
the sequence $1=t_{1}<t_{2}<\dots<t_{k}$ defined by

$\displaystyle
t_{i}\vcentcolon=\Big{\lfloor}\log\frac{1}{p_{i}+\dots+p_{k}}\Big{\rfloor}+i.$

The same analysis yield the desired $\exp(-O(2^{k}))$ lower bound. ∎

Simply rephrasing Lemma 7.31 in terms of depth-$1$ $\mathit{AC^{0}}$ formulas,
we get the following:

######  Corollary 7.32.

For every $k$-variable $\Pi_{1}$ or $\Sigma_{1}$ formula G (i.e., an $m$-ary
$\bigwedge$ or $\bigvee$ of literals, where $m$ may be arbitrarily large
relative to $k$), there exists an equivalent strict DeMorgan formula
$\textup{{G}}^{\ast}$ of $\llbracket\hskip 0.59998pt\rrbracket{}$-depth at
most $1$ such that for all $t\geq 2^{k}$, we have

$\displaystyle\operatorname*{\mathds{P}}_{\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})}\big{[}\
\textup{{strict}}(\textup{{g}})=\textup{{G}}^{\ast}\
\big{]}\geq\exp(-O(2^{k})).$

###### Proof.

Without loss of generality, it suffices to consider the case that G is a
monotone $\Pi_{1}$ formula of size $m=m_{1}+\dots+m_{k}$ with $m_{i}$ leaves
labeled by the positive literal $X_{i}$, where $m_{1}\geq\dots\geq m_{k}\geq
1$. Further assume w.l.o.g. that $m$ is a power of $2$. Letting
$p_{i}\vcentcolon=\frac{m_{i}}{m}$ for $i\in[k]$, note that
$\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})$ is identical (after renaming
$\wedge$ to $\cup$ and $X_{i}$ to $E_{i}$) to the random join tree
$\bm{T}_{\log(tm)}$ of Lemma 7.31. Since $\log(tm)\geq k+\log m\geq
k+\log\frac{1}{p_{k}}$, Lemma 7.31 implies

$\displaystyle\operatorname*{\mathds{P}}_{\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})}\big{[}\
\textup{{strict}}(\textup{{g}})=\llbracket
X_{1},\dots,X_{k}\rrbracket_{\wedge}\ \big{]}$
$\displaystyle\geq\exp(-O(2^{k})).$

The desired statement is proved by letting
$\textup{{G}}^{\ast}\vcentcolon=\llbracket
X_{1},\dots,X_{k}\rrbracket_{\wedge}$, which is clearly strict, equivalent to
G, and has $\llbracket\hskip 0.59998pt\rrbracket{}$-depth $1$. ∎

The next lemma extends Corollary 7.32 to $\mathit{AC^{0}}$ formulas G beyond
depth $1$. For the analysis to work out, we consider the distribution
$\mathscr{D}_{t}(\textup{{G}})$ for larger $t$, which allows us to condition
on the event that $\textup{{g}}_{0}\sim\mathscr{D}_{t}(\textup{{G}}_{0})$ is
equivalent to $\textup{{G}}_{0}$ for every sub-formula $\textup{{G}}_{0}$ of
G.

######  Lemma 7.33.

For every $k$-variable $\mathit{AC^{0}}$ formula G of depth $d$, there exists
an equivalent strict DeMorgan formula $\textup{{G}}^{\ast}$ of
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$ such that for all
$t\geq 2^{2^{2^{k}}}\cdot(\log\mathrm{size}(\textup{{G}}))^{3}$, we have

$\displaystyle\operatorname*{\mathds{P}}_{\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})}\big{[}\
\textup{{strict}}(\textup{{g}})=\textup{{G}}^{\ast}\ \big{]}\geq
2^{-\exp(O(d2^{2^{k}}))}.$

###### Proof.

The case $d=0$ is trivial and Corollary 7.32 proves the case $d=1$.

For the induction step when $d\geq 2$, assume that
$\textup{{G}}=\bigwedge_{i=1}^{m}\textup{{G}}_{i}$. (The argument for
$\textup{{G}}=\bigvee_{i=1}^{m}\textup{{G}}_{i}$ is identical after swapping
$\vee$ for $\wedge$.) By the induction hypothesis, there exist $k$-variable
DeMorgan formulas $\textup{{G}}_{1}^{\ast},\dots,\textup{{G}}_{m}^{\ast}$
which satisfy the lemma with respect to subformulas
$\textup{{G}}_{1},\dots,\textup{{G}}_{m}$.

Let $h_{1},\dots,h_{s}:\\{0,1\\}^{k}\to\\{0,1\\}$ enumerate the distinct
functions computed by sub-formulas $\textup{{G}}_{1},\dots,\textup{{G}}_{m}$,
ordered such that $m_{1}\geq\dots\geq m_{s}$ where

$\displaystyle m_{j}\vcentcolon=\big{|}\big{\\{}i\in[m]:\textup{{G}}_{i}\text{
computes }h_{j}\big{\\}}\big{|}.$

Next, for each $j\in[s]$, consider the set

$\displaystyle\big{\\{}\textup{{G}}_{i}^{\ast}:i\in[m]\text{ such that
$\textup{{G}}_{i}$ computes }h_{j}\big{\\}}.$

Each element of this set is a strict $k$-variable DeMorgan formula of
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d-1$, hence the size
of this set is at most $2^{2^{d(k+1)}}$ by Lemma 7.28. It follows that there
exist strict $k$-variable DeMorgan formulas
$\textup{{h}}_{1},\dots,\textup{{h}}_{s}$ of $\llbracket\hskip
0.59998pt\rrbracket{}$-depth at most $d-1$ such that for all $j\in[s]$,

$\displaystyle\big{|}\big{\\{}i\in[m]:\textup{{G}}_{i}^{\ast}=\textup{{h}}_{j}\big{\\}}\big{|}\geq\frac{m_{j}}{2^{2^{d(k+1)}}}.$

Let $J=\\{j_{1}<\dots<j_{r}\\}\subseteq[s]$ be the subset of indices defined
by

$\displaystyle J\vcentcolon=\big{\\{}j\in[s]:h_{1}\wedge\dots\wedge
h_{j-1}\not\equiv h_{1}\wedge\dots\wedge h_{j}\big{\\}}.$

Note that whereas $s\leq 2^{2^{k}}$, we have $r\leq 2^{k}$ since this is the
maximum length of a strictly decreasing sequence of nonzero functions
$\\{0,1\\}^{k}\to\\{0,1\\}$ (assuming w.l.o.g. that $\textup{{G}}\not\equiv
0$).

At last, we choose $\textup{{G}}^{\ast}$ to be the formula
$\llbracket\textup{{h}}_{j_{1}},\dots,\textup{{h}}_{j_{r}}\rrbracket_{\wedge}$.
Observe that $\textup{{G}}^{\ast}$ is equivalent to G and has
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$. Moreover, it is
strict and satisfies
$\textup{{strict}}(\llbracket\textup{{h}}_{1},\dots,\textup{{h}}_{s}\rrbracket_{\wedge})=\textup{{G}}^{\ast}$.

Onto the probabilistic analysis. We generate
$\textup{{g}}\sim\mathscr{D}_{t}(\textup{{G}})$ a balanced tree of binary
$\wedge$-gates with subformulas
$\textup{{g}}_{\bm{\iota}_{1}},\dots,\textup{{g}}_{\bm{\iota}_{tm}}$ feeding
in for independent uniform random $\bm{\iota}_{1},\dots,\bm{\iota}_{tm}\in[m]$
and $\textup{{g}}_{i}\sim\mathscr{D}_{t}(\textup{{G}}_{i})$ ($i\in[m]$). Note
that our choice of $t$ ensures that $\textup{{g}}_{i}\equiv\textup{{G}}_{i}$
for all $i\in[m]$ with probability $1-o(1)$. Let us henceforth automatically
condition on this event in all instances of
$\operatorname*{\mathds{P}}[\,\cdot\,]$ below.

By the induction hypothesis and our choice of formulas
$\textup{{h}}_{1},\dots,\textup{{h}}_{s}$, for all indices $j\in[s]$ and
$q\in[tm]$, we have

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q}})=\textup{{h}}_{j}\ \big{|}\
\textup{{G}}_{\bm{\iota}_{q}}\textup{ computes }h_{j}\ \big{]}$
$\displaystyle\geq 2^{-2^{d(k+1)}}\cdot\operatorname*{\mathds{P}}\big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q}})=G_{\bm{\iota}_{q}}^{\ast}\
\big{]}$ $\displaystyle\geq 2^{-2^{d(k+1)}}\cdot
2^{-\exp(O((d-1)2^{2^{k}}))}.$

Now consider the top $\log(tm)$ layers of g, which we view as a random tree of
binary $\wedge$ gates with inputs labeled by the functions computed at
subformulas
$\textup{{g}}_{\bm{\iota}_{1}},\dots,\textup{{g}}_{\bm{\iota}_{tm}}$ (elements
of the set $\\{h_{1},\dots,h_{s}\\}$). Call this tree $T(\textup{{g}})$.
Viewing $T(\textup{{g}})$ as a join tree over single-edge graphs
$E_{1},\dots,E_{s}$ (or, alternatively, viewing $T(\textup{{g}})$ as a
DeMorgan formula over literals corresponding to functions
$h_{1},\dots,h_{s}$), Lemma 7.31 (or from a different perspective Corollary
7.32) tells us

$\displaystyle\operatorname*{\mathds{P}}\big{[}\
\underbrace{\mathit{strict}(T(\textup{{g}}))=\llbracket
h_{1},\dots,h_{s}\rrbracket_{\wedge}}_{\textstyle\textup{call this event
}\mathcal{E}}\ \big{]}\geq 2^{-c2^{s}}$

for some absolute constant $c$ determined by Lemma 7.31.

Conditioned on event $\mathcal{E}$, there exist $2^{s}$ indices — name them
$1\leq q_{1}<\dots<q_{2^{s}}<tm$ — which embed the leaves of $\llbracket
h_{1},\dots,h_{s}\rrbracket_{\wedge}$ among the leaves of $T(\textup{{g}})$.
By definition of this sequence, formulas
$\textup{{g}}_{\bm{\iota}_{q_{1}}},\dots,\textup{{g}}_{\bm{\iota}_{q_{2^{s}}}}$
compute functions $h_{1},h_{2},h_{1},h_{3},\dots,h_{1},h_{2},h_{1},h_{s}$. Now
observe that

$\displaystyle\operatorname*{\mathds{P}}\big{[}\ $
$\displaystyle\textup{{strict}}(\textup{{g}})=\textup{{G}}^{\ast}\ \big{|}\
\mathcal{E}\ \big{]}$ $\displaystyle=\operatorname*{\mathds{P}}\Big{[}\
\textup{{strict}}(\textup{{g}})=\textup{{strict}}(\llbracket\textup{{h}}_{1},\dots,\textup{{h}}_{s}\rrbracket_{\wedge})\
\Big{|}\ \mathcal{E}\ \Big{]}$
$\displaystyle\geq\operatorname*{\mathds{P}}\Big{[}\
(\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{1}}}),\dots,\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{2^{s}}}}))=(\textup{{h}}_{1},\textup{{h}}_{2},\textup{{h}}_{1},\textup{{h}}_{3},\dots,\textup{{h}}_{1},\textup{{h}}_{2},\textup{{h}}_{1},\textup{{h}}_{s})\
\Big{|}\ \mathcal{E}\ \Big{]}\vphantom{\Big{|}}$
$\displaystyle=\operatorname*{\mathds{P}}\Big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{1}}})=\textup{{h}}_{1}\
\Big{|}\ \textup{{G}}_{\bm{\iota}_{q_{1}}}\textup{ computes }h_{1}\
\Big{]}\cdot\operatorname*{\mathds{P}}\Big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{2}}})=\textup{{h}}_{2}\
\Big{|}\ \textup{{G}}_{\bm{\iota}_{q_{2}}}\textup{ computes }h_{2}\
\Big{]}\cdot\,\ldots\mbox{}$ $\displaystyle\quad\
\mbox{}\ldots\,\cdot\operatorname*{\mathds{P}}\Big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{2^{s}-1}}})=\textup{{h}}_{1}\
\Big{|}\ \textup{{G}}_{\bm{\iota}_{q_{2^{s}-1}}}\textup{ computes }h_{1}\
\Big{]}\cdot\operatorname*{\mathds{P}}\Big{[}\
\textup{{strict}}(\textup{{g}}_{\bm{\iota}_{q_{2^{s}}}})=\textup{{h}}_{s}\
\Big{|}\ \textup{{G}}_{\bm{\iota}_{q_{2^{s}}}}\textup{ computes }h_{s}\
\Big{]}$ $\displaystyle\geq\Big{(}2^{-2^{d(k+1)}}\cdot
2^{-\exp(O((d-1)2^{2^{k}}))}\Big{)}{}^{2^{s}}.$

Finally, we obtain the desired bound

$\displaystyle\vphantom{\Big{|}}\operatorname*{\mathds{P}}\big{[}\
\textup{{strict}}(\textup{{g}})=\textup{{G}}^{\ast}\
\big{]}\geq\operatorname*{\mathds{P}}\big{[}\ \mathcal{E}\
\big{]}\cdot\operatorname*{\mathds{P}}\big{[}\
\textup{{strict}}(\textup{{g}})=\textup{{G}}^{\ast}\ \big{|}\ \mathcal{E}\
\big{]}$ $\displaystyle\geq 2^{-c2^{s}}\cdot\Big{(}2^{-2^{d(k+1)}}\cdot
2^{-\exp(O((d-1)2^{2^{k}}))}\Big{)}{}^{2^{s}}$
$\displaystyle\geq\Big{(}2^{-c}\cdot 2^{-2^{d(k+1)}}\cdot
2^{-\exp(O((d-1)2^{2^{k}}))}\Big{)}\smash{{}^{2^{2^{2^{k}}}}}$
$\displaystyle\geq 2^{-\exp(O(d2^{2^{k}}))}$

for an appropriate big-$O$ constant depending on the constant $c$. ∎

###  7.8 Tradeoff (II)- for non-monotone $\mathit{AC^{0}}$ formulas

We are ready to prove size-depth tradeoff (II)- for non-monotone
$\mathit{AC^{0}}$ formulas. The proof has an overall similar structure to the
proof of tradeoff (I)+ in §7.5.

######  Theorem 7.34 (Tradeoff (II)- of Theorem 1.6).

Suppose that F is a depth-$d$ $\mathit{AC^{0}}$ formula which computes
$\textup{{sub-pmm}}_{n,k}$ where $k\leq\log^{\ast}n$ and $d\leq\log k$. Then F
has size $n^{\Omega(dk^{1/2d})}$.

By a simple additional argument, the same $n^{\Omega(dk^{1/2d})}$ lower bound
may actually be obtained for $\mathit{AC^{0}}$ formulas of depth $d+1$
(precisely matching the statement of tradeoff (II)- in Theorem 1.6). We
present the lower bound for depth-$d$ $\mathit{AC^{0}}$ formulas for
simplicity sake, since the factor $2$ in the second exponent is anyway
probably not optimal.

###### Proof.

Without loss of generality, assume that F has size at most $n^{k}$, since this
is greater than the lower bound we wish to show. Let

$\displaystyle t\vcentcolon=2^{2^{2^{k}}}\cdot(\log n)^{4}$

and consider the randomized balanced DeMorgan conversion
$\textup{{f}}\sim\mathscr{D}_{t}(\textup{{F}})$. Lemma 7.24 implies that, with
probability $1-o(1)$, the $G$-relations
$\mathcal{N}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})$ are pathsets for all
subformulas $\textup{{f}}_{0}$ of f and subgraphs
$G\subseteq\mathsf{Path}_{k}$. We proceed with our analysis conditioned on
this almost sure event.

For each $\textup{{f}}_{0}$ and $G$, we define a covering
$\bigcup_{T\in\mathscr{T}_{G}}\mathcal{N}^{(T)}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})=\mathcal{N}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})$
by essentially Definition 7.15, except that in the induction step where
$T=\langle T_{1},T_{2}\rangle$, we are now forced to treat the case
$\textup{{f}}_{0}=\textup{{f}}_{1}\vee\textup{{f}}_{2}$ the same as
$\textup{{f}}_{0}=f_{1}\wedge\textup{{f}}_{2}$, in both cases defining

$\displaystyle\mathcal{N}_{G}^{(T)}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})\vcentcolon=\mathcal{N}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})\cap\Big{(}\mathcal{N}^{(T)}_{G}(\textup{{f}}_{1}^{\cup{\bm{\Xi}}})\cup\mathcal{N}^{(T)}_{G}(\textup{{f}}_{2}^{\cup{\bm{\Xi}}})\cup\Big{(}\mathcal{N}^{(T_{1})}_{G_{1}}(\textup{{f}}_{1}^{\cup{\bm{\Xi}}})\bowtie\mathcal{N}^{(T_{2})}_{G_{2}}(\textup{{f}}_{2}^{\cup{\bm{\Xi}}})\Big{)}\Big{)}.$

By Lemma 7.21,
$\mathcal{N}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}})$ almost surely
has density at least $\frac{1}{2n^{2}}$. For each
$\alpha\in\mathcal{N}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}})$, we
consider the restricted $k$-variable depth-$d$ $\mathit{AC^{0}}$ formula

$\displaystyle\textup{{G}}_{\alpha}\vcentcolon=\textup{{F}}^{\cup{\bm{\Xi}}}{\upharpoonright}\mathsf{Path}_{k}^{(\alpha)}$

obtained by F by fixing variables corresponding to ${\bm{\Xi}}$ to $1$, and
all other variables except the $k$ edges of $\mathsf{Path}_{k}^{(\alpha)}$ to
$0$.

We now invoke the key Lemma 7.33 to obtain, for each
$\alpha\in\mathcal{N}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}})$, a
strict DeMorgan formula $\textup{{G}}_{\alpha}^{\ast}$ of $\llbracket\hskip
0.59998pt\rrbracket{}$-depth at most $d$, which is equivalent to
$\textup{{G}}_{\alpha}$ (hence depends on all $k$ variables) and satisfies

$\displaystyle\operatorname*{\mathds{P}}_{\textup{{g}}_{\alpha}\sim\mathscr{D}_{t}(\textup{{G}}_{\alpha})}\big{[}\
\textup{{strict}}(\textup{{g}}_{\alpha})=\textup{{G}}_{\alpha}^{\ast}\
\big{]}\geq 2^{-\exp(O(d2^{2^{k}}))}.$

Let $T_{\alpha}^{\ast}$ denote the strict support tree of
$\textup{{G}}_{\alpha}^{\ast}$:

$\displaystyle
T_{\alpha}^{\ast}\vcentcolon=\mathit{strict}(S(\textup{{G}}_{\alpha}^{\ast})).$

Note that $T_{\alpha}^{\ast}$ is a strict $\mathsf{Path}_{k}$-join tree since
$\textup{{G}}_{\alpha}$
($=\textup{{F}}^{\cup{\bm{\Xi}}}{\upharpoonright}\mathsf{Path}_{k}^{(\alpha)}$)
depends on all variables corresponding to edges of
$\mathsf{Path}_{k}^{(\alpha)}$. Moreover, $T_{\alpha}^{\ast}$ has
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$ (i.e., at most the
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth of
$\textup{{G}}_{\alpha}^{\ast}$) by Lemma 7.30.

Next, we observe that the distribution of
$\textup{{g}}_{\alpha}\sim\mathscr{D}_{t}(\textup{{G}}_{\alpha})$ — that is,
$\textup{{g}}_{\alpha}\sim\mathscr{D}_{t}(\textup{{F}}^{\cup{\bm{\Xi}}}{\upharpoonright}\mathsf{Path}_{k}^{(\alpha)})$
— is identical to distribution of
$\textup{{f}}{\upharpoonright}\mathsf{Path}_{k}^{(\alpha)}$ where
$\textup{{f}}\sim\mathscr{D}_{t}(\textup{{F}}^{\cup{\bm{\Xi}}})$. Generating
$\textup{{g}}_{\alpha}$ as
$\textup{{f}}{\upharpoonright}\mathsf{Path}_{k}^{(\alpha)}$, we have the
following implication:

$\displaystyle\textup{{strict}}(\textup{{g}}_{\alpha})=\textup{{G}}_{\alpha}^{\ast}\
\Longrightarrow\
\alpha\in\mathcal{N}^{(T_{\alpha}^{\ast})}_{\mathsf{Path}_{k}}(\textup{{f}}).$

Since there are at most $2^{k^{d+1}}$ strict $\mathsf{Path}_{k}$-join trees of
$\llbracket\hskip 0.59998pt\rrbracket{}$-depth at most $d$ (by Lemma 7.14), we
may fix one such join tree $T^{\ast}$ such that

$\displaystyle\mu(\\{\alpha\in\mathcal{N}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}):T_{\alpha}^{\ast}=T^{\ast}\\})\geq\frac{1}{2^{k^{d+1}}}\cdot\mu(\mathcal{N}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}))\geq\frac{1}{2^{k^{d+1}}\cdot
2n^{2}}.$

It follows that

$\displaystyle\mu(\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}))\geq\frac{1}{2^{\exp(O(d2^{2^{k}}))}\cdot
2^{k^{d+1}}\cdot 2n^{2}}=\frac{1}{n^{2+o(1)}}.$

Recall that the random DeMorgan formula
$\textup{{f}}\sim\mathscr{D}_{t}(\textup{{F}})$ has depth at most
$d\cdot\lceil\log(t\cdot\mathrm{size}(\textup{{F}}))\rceil$ and size at most
$t^{d}\cdot\mathrm{size}(\textup{{F}})$. Moreover, with probability $1-o(1)$,
functions $\textup{{F}}^{\cup{\bm{\Xi}}}$ and $\textup{{f}}^{\cup{\bm{\Xi}}}$
agree on all inputs of Hamming weight $\leq k$ (by a union bound), hence
$\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}})=\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{f}}^{\cup{\bm{\Xi}}}).$

Since $\mathcal{N}_{G}(\textup{{f}}_{0}^{\cup{\bm{\Xi}}})$ are pathsets for
all $\textup{{f}}_{0}$ of f and $G\subseteq\mathsf{Path}_{k}$, Lemma 7.23
yields an upper bound on pathset complexity:

$\displaystyle\chi_{T^{\ast}}(\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}))\vphantom{\Big{|}}$
$\displaystyle=\chi_{T^{\ast}}(\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{f}}^{\cup{\bm{\Xi}}}))$
$\displaystyle\leq\big{(}0pt(\textup{{f}}^{\cup{\bm{\Xi}}})+1\big{)}{}^{k}\cdot\mathrm{size}(\textup{{f}}^{\cup{\bm{\Xi}}})$
$\displaystyle=O\big{(}d\cdot\log(t\cdot\mathrm{size}(\textup{{F}}))\big{)}{}^{k}\cdot
t^{d}\cdot\mathrm{size}(\textup{{F}})$ $\displaystyle\leq
O\big{(}d\cdot\log(2^{2^{2^{k}}}\cdot(\log n)^{4}\cdot
n^{k})\big{)}{}^{k}\cdot 2^{d2^{2^{k}}}\cdot(\log
n)^{4d}\cdot\mathrm{size}(\textup{{F}})$
$\displaystyle=n^{o(1)}\cdot\mathrm{size}(\textup{{F}}).$

On the other hand, since $T^{\ast}$ has $\llbracket\hskip
0.59998pt\rrbracket{}$-depth at most $d$, Corollary 6.12(II) provides the
lower bound

$\displaystyle\chi_{T^{\ast}}(\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}))$
$\displaystyle\geq
n^{\Omega(dk^{1/2d})}\cdot\mu(\mathcal{N}^{(T^{\ast})}_{\mathsf{Path}_{k}}(\textup{{F}}^{\cup{\bm{\Xi}}}))\geq\frac{n^{\Omega(dk^{1/2d})}}{n^{2+o(1)}}.$

Combining these inequalities, we conclude that F has size
$n^{\Omega(dk^{1/2d})}$ as required. ∎

######  Remark 7.35.

This proof shows that the range $k\leq\log^{\ast}n$ can be extended to $k\leq
0.99\log\log\log\log n$, small enough to ensure that
$2^{\exp(O(d2^{\smash{2^{k}}}))}=n^{o(1)}$. We have made little effort to
optimize the range of $k$ and expect it can be extended further, potentially
to $\log\log n$.

## Acknowledgements

This paper was partially written during visits to the Tokyo Institute of
Technology and the National Institute of Informatics. The author is grateful
to the anonymous referees of STOC 2024 for valuable feedback on an earlier
draft of this paper.

## References

  * [1] M. Ajtai.  $\Sigma^{1}_{1}$ formulae on finite structures.  Annals of Pure and Applied Logic, 24:1–48, 1983.
  * [2] M. Ajtai.  First-order definability on finite structures.  Annals of Pure and Applied Logic, 45(3):211–225, 1989.
  * [3] D. A. Barrington.  Bounded-width polynomial-size branching programs recognize exactly those languages in nc.  In Proc. 18th ACM Symposium on Theory of Computing, pages 1–5, 1986.
  * [4] P. Beame, R. Impagliazzo, and T. Pitassi.  Improved depth lower bounds for small distance connectivity.  Computational Complexity, 7(4):325–345, 1998.
  * [5] S. Bellantoni, T. Pitassi, and A. Urquhart.  Approximation and small-depth Frege proofs.  SIAM Journal on Computing, 21(6):1161–1179, 1992.
  * [6] S. J. Berkowitz.  On some relationships between monotone and nonmonotone circuit complexity.  Technical report, Department of Computer Science, University of Toronto, 1982.
  * [7] X. Chen, I. Oliveira, R. A. Servedio, and L.-Y. Tan.  Near-optimal small-depth lower bounds for small distance connectivity.  In Proc. 48th ACM Symposium on Theory of Computing, pages 612–625, 2016.
  * [8] S. A. Cook and P. McKenzie.  Problems complete for deterministic logarithmic space.  Journal of Algorithms, 8(3):385–394, 1987.
  * [9] M. L. Furst, J. B. Saxe, and M. Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Mathematical Systems Theory, 17:13–27, 1984.
  * [10] T. Hagerup.  Fast parallel generation of random permutations.  In Proc. 18th International Colloquium on Automata, Languages and Programming:, pages 405–416. Springer, 1991.
  * [11] J. Håstad.  Almost optimal lower bounds for small depth circuits.  In Proc. 18th ACM Symposium on Theory of Computing, pages 6–20, 1986.
  * [12] J. Håstad.  The shrinkage exponent of de Morgan formulas is 2.  SIAM Journal on Computing, 27(1):48–64, 1998.
  * [13] W. He and B. Rossman.  Symmetric formulas for products of permutations.  In 14th Innovations in Theoretical Computer Science Conference (ITCS), volume 251, pages 68:1–68:23, 2023.
  * [14] S. Janson.  Poisson approximation for large deviations.  Random Structures and Algorithms, 1(2):221–229, 1990.
  * [15] D. Kush and B. Rossman.  Tree-depth and the formula complexity of subgraph isomorphism.  SIAM Journal on Computing, 52(1):273–325, 2023.
  * [16] G. Lagarde, N. Limaye, and S. Srinivasan.  Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees.  computational complexity, 28:471–542, 2019.
  * [17] N. Limaye, S. Srinivasan, and S. Tavenas.  Superpolynomial lower bounds against low-depth algebraic circuits.  In Proc. 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pages 804–814, 2022.
  * [18] Y. Matias and U. Vishkin.  Converting high probability into nearly-constant time—with applications to parallel hashing.  In Proc. 23rd ACM Symposium on the Theory of Computing, pages 307–316, 1991.
  * [19] C. Mereghetti and B. Palano.  Threshold circuits for iterated matrix product and powering.  RAIRO-Theoretical Informatics and Applications, 34(1):39–46, 2000\.
  * [20] A. A. Razborov.  Lower bounds on the size of constant-depth networks over a complete basis with logical addition.  Mathematicheskie Zametki, 41(4):598–607, 1987.
  * [21] B. Rossman.  Correlation bounds against monotone NC${}^{\text{1}}$.  In 30th Conference on Computational Complexity, volume 33 of LIPIcs, pages 392–411, 2015.
  * [22] B. Rossman.  The average sensitivity of bounded-depth formulas.  Computational Complexity, 27(2):209–223, 2018.
  * [23] B. Rossman.  Formulas versus circuits for small distance connectivity.  SIAM Journal on Computing, 47(5):1986–2028, 2018.
  * [24] B. Rossman.  Lower bounds for subgraph isomorphism.  In Proc. International Congress of Mathematicians (ICM 2018, Rio de Janeiro), volume 3, pages 3409–3430, 2018.
  * [25] W. J. Savitch.  Relationships between nondeterministic and deterministic tape complexities.  Journal of computer and system sciences, 4(2):177–192, 1970.
  * [26] R. Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82, 1987.
  * [27] A. Tal.  Shrinkage of De Morgan formulae by spectral techniques.  In 55th Annual IEEE Symposium on Foundations of Computer Science, pages 551–560, 2014.
  * [28] S. Tavenas, N. Limaye, and S. Srinivasan.  Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 416–425, 2022.
  * [29] E. Viola.  The complexity of distributions.  SIAM Journal on Computing, 41(1):191–218, 2012.
  * [30] F. Wang.  On circuit complexity classes and iterated matrix multiplication.  Rutgers The State University of New Jersey, School of Graduate Studies, 2012.