An average-case depth hierarchy theorem for Boolean circuits

Introduction

The study of small-depth Boolean circuits is one of the great success stories of complexity theory. The exponential lower bounds against constant-depth AND-OR-NOT circuits [Yao85, Hås86a, Raz87, Smo87] remain among our strongest unconditional lower bounds against concrete models of computation, and the techniques developed to prove these results have led to significant advances in computational learning theory [LMN93, Man95], pseudorandomness [Nis91, Baz09, Raz09, Bra10], proof complexity [PBI93, Ajt94, KPW95], structural complexity [Yao85, Hås86a, Cai86], and even algorithm design [Wil14a, Wil14b, AWY15].

In addition to worst-case lower bounds against small-depth circuits, average-case lower bounds, or correlation bounds, have also received significant attention. As one recent example, Impagliazzo, Matthews, Paturi [IMP12] and Håstad [Hås14] independently obtained optimal bounds on the correlation of the parity function with small-depth circuits, capping off a long line of work on the problem [Ajt83, Yao85, Hås86a, Cai86, Bab87, BIS12]. These results establish strong limits on the computational power of constant-depth circuits, showing that their agreement with the parity function can only be an exponentially small fraction better than that of a constant function.

In this paper we will be concerned with average-case complexity within the class of small-depth circuits: our goal is to understand the computational power of depth-$d$ circuits relative to those of strictly smaller depth. Our main result is an average-case depth hierarchy theorem for small-depth circuits:

Let $2\leq d\leq{\frac{c\sqrt{\log n}}{\log\log n}}$, where $c>0$ is an absolute constant, and $\mathsf{Sipser}_{d}$ be the explicit $n$-variable read-once monotone depth-$d$ formula described in Section 6. Then any circuit $C$ of depth at most $d-1$ and size at most $S=2^{n^{{\frac{1}{6(d-1)}}}}$ over $\{0,1\}^{n}$ agrees with $\mathsf{Sipser}_{d}$ on at most $({\frac{1}{2}}+n^{-\Omega(1/d)})\cdot 2^{n}$ inputs.

(We actually prove two incomparable lower bounds, each of which implies Theorem 1 as a special case. Roughly speaking, the first of these says that $\mathsf{Sipser}_{d}$ cannot be approximated by size-$S$, depth-$d$ circuits which have significantly smaller bottom fan-in than $\mathsf{Sipser}_{d}$, and the second of these says that $\mathsf{Sipser}_{d}$ cannot be approximated by size-$S$, depth-$d$ circuits with a different top-level output gate than $\mathsf{Sipser}_{d}$.)

Theorem 1 is an average-case extension of the worst-case depth hierarchy theorems of Sipser, Yao, and Håstad [Sip83, Yao85, Hås86a], and answers an open problem of Håstad [Hås86a] (which also appears in [Hås86b, Hås89]). We discuss the background and context for Theorem 1 in Section 1.1, and state our two main lower bounds more precisely in Section 1.2.

We give two applications of our main result, one in structural complexity and the other in the analysis of Boolean functions. First, via a classical connection between small-depth computation and the polynomial hierarchy [FSS81, Sip83], Theorem 1 implies that the polynomial hierarchy is infinite relative to a random oracle:

This resolves a well-known conjecture in structural complexity, which first appeared in [Hås86a, Cai86, Bab87] and has subsequently been discussed in a wide range of surveys [Joh86, Hem94, ST95, HRZ95, VW97, Aar], textbooks [DK00, HO02], and research papers [Hås86b, Hås89, Tar89, For99, Aar10a]. (Indeed, the results of [Hås86a, Cai86, Bab87], along with much of the pioneering work on lower bounds against small-depth circuits in the 1980’s, were largely motivated by the aforementioned connection to the polynomial hierarchy.) See Section 2 for details.

There are functions $d(n)=\omega_{n}(1)$ and $S(n)=\exp((\log n)^{\omega_{n}(1)})$ such that there is a monotone $f:\{0,1\}^{n}\to\{0,1\}$ with total influence $\mathbf{Inf}(f)=O(\log n)$, but any circuit $C$ that has depth $d(n)$ and agrees with $f$ on at least $({\frac{1}{2}}+o_{n}(1))\cdot 2^{n}$ inputs in $\{0,1\}^{n}$ must have size greater than $S(n)$.

Theorem 3 significantly strengthens O’Donnell and Wimmer’s counterexample [OW07] to a conjecture of Benjamini, Kalai, and Schramm [BKS99], and shows that the total influence bound of [LMN93, Bop97] does not admit even a very weak approximate converse. See Section 3 for details.

1 Previous work

In this subsection we discuss previous work related to our average-case depth hierarchy theorem. We discuss the background and context for our applications, Theorems 2 and 3, in Sections 2 and 3 respectively.

To the best of our knowledge, the first progress towards an average-case depth hierarchy theorem for small-depth circuits was made by O’Donnell and Wimmer [OW07]. They constructed a linear-size depth-$3$ circuit $F$ and proved that any depth-$2$ circuit that approximates $F$ must have size $2^{\Omega(n/\log n)}$:

Then any depth-$2$ circuit $C$ on $2n$ variables that has size $2^{O(n/\log n)}$ agrees with $F$ on at most a $0.99$-fraction of the $2^{2n}$ inputs. (Note that $F$ is computed by a linear-size depth-3 circuit.)

2 Our main lower bounds

We close this section with precise statements of our two main lower bound results, a discussion of the (near)-optimality of our correlation bounds, and a very high-level overview of our techniques.

For $2\leq d\leq{\frac{c\sqrt{\log n}}{\log\log n}}$, the $n$-variable $\mathsf{Sipser}_{d}$ function has the following property: Any depth-$d$ circuit $C:\{0,1\}^{n}\to\{0,1\}$ of size at most $S=2^{n^{{\frac{1}{6(d-1)}}}}$ and bottom fan-in ${\frac{\log n}{10(d-1)}}$ agrees with $\mathsf{Sipser}_{d}$ on at most $(\frac{1}{2}+n^{-\Omega(1/d)})\cdot 2^{n}$ inputs.

For $2\leq d\leq{\frac{c\sqrt{\log n}}{\log\log n}}$, the $n$-variable $\mathsf{Sipser}_{d}$ function has the following property: Any depth-$d$ circuit $C:\{0,1\}^{n}\to\{0,1\}$ of size at most $S=2^{n^{{\frac{1}{6(d-1)}}}}$ and the opposite alternation pattern to $\mathsf{Sipser}_{d}$ (i.e. its top-level output gate is $\mathsf{OR}$ if $\mathsf{Sipser}_{d}$’s is $\mathsf{AND}$ and vice versa) agrees with $\mathsf{Sipser}_{d}$ on at most $(\frac{1}{2}+n^{-\Omega(1/d)})\cdot 2^{n}$ inputs.

Clearly both these results imply Theorem 1 as a special case, since any size-$S$ depth-$(d-1)$ circuit may be viewed as a size-$S$ depth-$d$ circuit satisfying the assumptions of Theorems 6 and 7.

For constant $d$, our main result shows that the depth-$d$ $\mathsf{Sipser}_{d}$ function has correlation at most $(1/2+n^{-\Omega(1)})$ with any subexponential-size circuit of depth $d-1$. Since $\mathsf{Sipser}_{d}$ is a monotone function, well-known results [BT96] imply that its correlation with some input variable $x_{i}$ or one of the constant functions 0,1 (trivial approximators of depth at most one) must be at least $(1/2+\Omega(1/n))$; thus significant improvements on our correlation bound cannot be achieved for this (or for any monotone) function.

What about non-monotone functions? If $\{f_{d}\}_{d\geq 2}$ is any family of $n$-variable functions computed by poly$(n)$-size, depth-$d$ circuits, the “discriminator lemma” of Hajnal et al. [HMP+93] implies that $f_{d}$ must have correlation at least $(1/2+n^{-O(1)})$ with one of the depth-$(d-1)$ circuits feeding into its topmost gate. Therefore a “$d$ versus $d-1$” depth hierarchy theorem for correlation $(1/2+n^{-\omega(1)})$ does not hold.

Our approach is based on random projections, a generalization of random restrictions. At a high level, we design a carefully chosen (adaptively chosen) sequence of random projections, and argue that with high probability under this sequence of random projections, (i) any circuit $C$ of the type specified in Theorem 6 or Theorem 7 “collapses,” while (ii) the $\mathsf{Sipser}_{d}$ function “retains structure,” and (iii) moreover this happens in such a way as to imply that the circuit $C$ must have originally been a very poor approximator for $\mathsf{Sipser}_{d}$ (before the random projections). Each of (i)–(iii) above requires significant work; see Section 4 for a much more detailed explanation of our techniques (and of why previous approaches were unable to successfully establish the result).

Application #1: Random oracles separate the polynomial hierarchy

The pioneering work on lower bounds against small-depth circuits in the 1980’s was largely motivated by a connection between small-depth computation and the polynomial hierarchy shown by Furst, Saxe, and Sipser [FSS81]. They gave a super-polynomial size lower bound for constant-depth circuits, proving that depth-$d$ circuits computing the $n$-variable parity function must have size $\Omega(n^{\log^{(3d-6)}n})$, where $\log^{(i)}n$ denotes the $i$-th iterated logarithm. They also showed that an improvement of this lower bound to super-quasipolynomial for constant-depth circuits (i.e. \Omega_{d}\big{(}2^{(\log n)^{k}}\big{)} for all constants $k$) would yield an oracle $A$ such that $\mathsf{PSPACE}^{A}\neq\mathsf{PH}^{A}$. Ajtai independently proved a stronger lower bound of $n^{\Omega_{d}(\log n)}$ [Ajt83]; his motivation came from finite model theory. Yao gave the first super-quasipolynomial lower bounds on the size of constant-depth circuits computing the parity function [Yao85], and shortly after Håstad proved the optimal lower bound of $\exp(\Omega(n^{1/(d-1)}))$ via his influential Switching Lemma [Hås86a].

Yao’s relativized separation of PSPACE from PH was improved qualitatively by Cai, who showed that the separation holds even relative to a random oracle [Cai86]. Leveraging the connection made by [FSS81], Cai accomplished this by proving correlation bounds against constant-depth circuits, showing that constant-depth circuits of sub-exponential size agree with the parity function only on a $(1/2+o_{n}(1))$ fraction of inputs. (Independent work of Babai [Bab87] gave a simpler proof of the same relativized separation.)

2 Background: The polynomial hierarchy is infinite relative to some oracle

Together, these results paint a fairly complete picture of the status of the $\mathsf{PSPACE}$ versus $\mathsf{PH}$ question in relativized worlds: not only does there exist an oracle $A$ such that $\mathsf{PSPACE}^{A}\neq\mathsf{PH}^{A}$, this separation holds relative to almost all oracles. A natural next step is to seek analogous results showing that the relativized polynomial hierarchy is infinite; we recall that the polynomial hierarchy being infinite implies $\mathsf{PSPACE}\neq\mathsf{PH}$, and furthermore, this implication relativizes. We begin with the following question, attributed to Albert Meyer in [BGS75]:

3 This work: The polynomial hierarchy is infinite relative to a random oracle

Given Håstad’s result, a natural goal is to complete our understanding of Meyer’s question by showing that the polynomial hierarchy is not just infinite with respect to some oracle, but in fact with respect to almost all oracles. Indeed, in [Hås86a, Hås86b, Hås89], Håstad poses the problem of extending his result to show this as an open question:

Question 1 also appears as the main open problem in [Cai86, Bab87]; as mentioned above, an affirmative answer to Question 1 would imply Cai and Babai’s result showing that $\mathsf{PSPACE}^{A}\neq\mathsf{PH}^{A}$ relative to a random oracle $A$. Further motivation for studying Question 1 comes from a surprising result of Book, who proved that the unrelativized polynomial hierarchy collapses if it collapses relative to a random oracle [Boo94]. Over the years Question 1 has been discussed in a wide range of surveys [Joh86, Hem94, ST95, HRZ95, VW97, Aar], textbooks [DK00, HO02], and research papers [Hås86b, Hås89, Tar89, For99, Aar10a].

We refer the reader to Chapter §7 of Håstad’s thesis [Hås86b] for a detailed exposition (and complete proofs) of the aforementioned connections between small-depth circuits and the polynomial hierarchy (in particular, for the proof of how Theorem 2 follows from Theorem 1).

Application #2: No approximate converse to Boppana–Linial–Mansour–Nisan

The famous result of Linial, Mansour, and Nisan gives strong bounds on Fourier concentration of small-depth circuits [LMN93]. As a corollary, they derive an upper bound on the total influence of small-depth circuits, showing that depth-$d$ size-$S$ circuits have total influence $(O(\log S))^{d}$. (We remind the reader that the total influence of an $n$-variable Boolean function $f$ is $\mathbf{Inf}(f):=\sum_{i=1}^{n}\mathbf{Inf}_{i}(f)$, where $\mathbf{Inf}_{i}(f)$ is the probability that flipping coordinate $i\in[n]$ of a uniform random input from $\{0,1\}^{n}$ causes the value of $f$ to change.) This was subsequently sharpened by Boppana via a simpler and more direct proof [Bop97]:

Let $f:\{0,1\}^{n}\to\{0,1\}$ be a computed by a size-$S$ depth-$d$ circuit. Then $\mathbf{Inf}(f)=(O(\log S))^{d-1}$.

(We note that Boppana’s bound is asymptotically tight by considering the parity function.) Several researchers have asked whether an approximate converse of some sort holds for Theorem 8:

If $f:\{0,1\}^{n}\to\{0,1\}$ has low total influence, is it the case that $f$ can be approximated to high accuracy by a small constant-depth circuit?

A result of this flavor, taken together with Theorem 8, would yield an elegant characterization of Boolean functions with low total influence. In this section we formulate a very weak approximate converse to Theorem 8 and show, as a consequence of our main result (Theorem 1), that even this weak converse does not hold.

An approximate converse to Theorem 8 was first conjectured by Benjamini, Kalai, and Schramm, with a very specific quantitative bound on how the size of the approximating circuit depends on its influence and depth [BKS99] (the conjecture also appears in the surveys [Kal00, KS05]). They posed the following:

For every $\varepsilon>0$ there is a constant $K=K(\varepsilon)$ such that the following holds: Every monotone $f:\{0,1\}^{n}\to\{0,1\}$ can be $\varepsilon$-approximated by a depth-$d$ circuit of size at most

(We associate a circuit with the Boolean function that it computes, and we say that a circuit $\varepsilon$-approximates a Boolean function $f$ if it agrees with $f$ on all but an $\varepsilon$-fraction of all inputs.) If true, the BKS conjecture would give a quantitatively strong converse to Theorem 8 for monotone functions.We remark that although the BKS conjecture was stated for monotone Boolean functions, it seems that (a priori) it could have been true for all Boolean functions: prior to [OW07], we are not aware of any counterexample to the BKS conjecture even if $f$ is allowed to be non-monotone. In addition, it would have important implications for the study of threshold phenomena in Erdös–Rényi random graphs, which is the context in which Benjamini, Kalai, and Schramm made their conjecture; we refer the reader to [BKS99] and Section 1.4 of [OW07] for a detailed discussion of this connection. However, the BKS conjecture was disproved by O’Donnell and Wimmer [OW07]. Their result (Theorem 5 in our introduction) disproves the case $d=2$ of the BKS conjecture, and the case $d>2$ is disproved by an easy argument which [OW07] give.

2 This work: Disproving a weak variant of the BKS conjecture

A significantly weaker variant of the BKS conjecture is the following:

For every $\varepsilon>0$ there is a $d=d(\varepsilon)$ and $K_{1}=K_{1}(\varepsilon),K_{2}=K_{2}(\varepsilon)$ such that the following holds: Every monotone $f:\{0,1\}^{n}\to\{0,1\}$ can be $\varepsilon$-approximated by a depth-$d$ circuit of size at most

Is it the case that for every $\varepsilon,C>0$, there are constants $d,k$ such that for every $f:\{0,1\}^{n}\to\{0,1\}$ with $\mathbf{Inf}(f)\leq C\log n$, there is a size-$n^{k}$, depth-$d$ circuit which $\varepsilon$-approximates $f$?

As a corollary of our main result (Theorem 1), we show that Conjecture 1 is false even for (suitable choices of) $\varepsilon={\frac{1}{2}}-o_{n}(1).$ Our counterexample also provides a strong negative answer to O’Donnell’s and Kalai–Hatami’s versions of Conjecture 1. We prove the following:

Consider the monotone Boolean function $f:\{0,1\}^{n}\to\{0,1\}$ corresponding to $\mathsf{Sipser}_{d}$ of Theorem 1 defined over the first $m=2^{{2^{\lfloor\sqrt{\log\log n}\rfloor}}}$ variables, and of depth $d=\lfloor\log\log m\rfloor+1=\lfloor\sqrt{\log\log n}\rfloor+1$. By Boppana’s theorem (Theorem 8), we have that

On the other hand, our main theorem (Theorem 1) implies that even circuits of depth $d-1=\lfloor\sqrt{\log\log n}\rfloor$ which agree with $f$ on $({\frac{1}{2}}+\delta(n))$ fraction of all inputs, where $\delta(n)=2^{-\Omega(2^{\lfloor\sqrt{\log\log n}\rfloor}/\lfloor\sqrt{\log\log n}\rfloor)}$, must have size at least

Our techniques

The method of random restrictions dates back to Subbotovskaya [Sub61] and continues to be an indispensable technique in circuit complexity. Focusing only on small-depth circuits, we mention that the random restriction method is the common essential ingredient underlying the landmark lower bounds discussed in the previous sections [FSS81, Ajt83, Sip83, Yao85, Hås86a, Cai86, Bab87, IMP12, Hås14].

We begin in Section 4.1 by describing the general framework for proving worst- and average-case lower bounds against small-depth circuits via the random restriction method. Within this framework, we sketch the now-standard proof of correlation bounds for the parity function based on Håstad’s Switching Lemma. We also recall why the lemma is not well-suited for proving a depth hierarchy theorem for small-depth circuits, hence necessitating the “blockwise variant” of the lemma that Håstad developed and applied to prove his (worst-case) depth hierarchy theorem. In Section 4.2 we highlight the difficulties that arise in extending Håstad’s depth hierarchy theorem to the average-case, and how our techniques — specifically, the notion of random projections — allow us to overcome these difficulties.

Suppose we would like to show that a target function $f:\{0,1\}^{n}\to\{0,1\}$ has small correlation with any size-$S$ depth-$d$ approximating circuit $C$ under the uniform distribution $\mathcal{U}$ over $\{0,1\}^{n}$. A standard approach is to construct a series of random restrictions $\{\mathcal{R}_{k}\}_{k\in\{2,\ldots,d\}}$ satisfying three properties:

Property 1: Approximator $C$ simplifies. The randomly-restricted circuit $C\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(2)}$, where ${\boldsymbol{\rho}}^{(k)}\leftarrow\mathcal{R}_{k}$ for $2\leq k\leq d$, should “collapse to a simple function” with high probability. This is typically shown via iterative applications of an appropriate “Switching Lemma for the $\mathcal{R}_{k}$’s ”, which shows that each random restriction ${\boldsymbol{\rho}}^{(k)}$ decreases the depth of the circuit $C\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(k-1)}$ by one with high probability. The upshot is that while $C$ is a depth-$d$ size-$S$ circuit, $C\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(2)}$ will be a small-depth decision tree, a “simple function”, with high probability.

Property 2: Target $f$ retains structure. In contrast with the approximating circuit, the target function $f$ should (roughly speaking) be resilient against the random restrictions ${\boldsymbol{\rho}}^{(k)}\leftarrow\mathcal{R}_{k}$. While the precise meaning of “resilient” depends on the specific application, the key property we need is that $f\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(2)}$ will with high probability be a “well-structured” function that is uncorrelated with any small-depth decision tree.

Together, these two properties imply that random restrictions of $f$ and $C$ are uncorrelated with high probability. Note that this already yields worst-case lower bounds, showing that $f:\{0,1\}^{n}\to\{0,1\}$ cannot be computed exactly by $C$. To obtain correlation bounds, we need to translate such a statement into the fact that $f$ and $C$ themselves are uncorrelated. For this we need the third key property of the random restrictions:

Property 3: Composition of $\mathcal{R}_{k}$’s completes to $\mathcal{U}$. Evaluating a Boolean function $h:\{0,1\}^{n}\to\{0,1\}$ on a random input $\mathbf{X}\leftarrow\mathcal{U}$ is equivalent to first applying random restrictions ${\boldsymbol{\rho}}^{(d)},\ldots,{\boldsymbol{\rho}}^{(2)}$ to $h$, and then evaluating the randomly-restricted function $h\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(2)}$ on $\mathbf{X}^{\prime}\leftarrow\mathcal{U}$.

For uniform-distribution correlation bounds against constant-depth circuits computing the parity function, the random restrictions are all drawn from $\mathcal{R}(p)$, the “standard” random restriction which independently sets each free variable to with probability $\frac{1}{2}(1-p)$, to $1$ with probability $\frac{1}{2}(1-p)$, and keeps it free with probability $p$. The main technical challenge arises in proving that Property 1 holds — this is precisely Håstad’s Switching Lemma — whereas Properties 2 and 3 are straightforward to show. For the second property, we note that

and so $\mathsf{Parity}_{n}\upharpoonright{\boldsymbol{\rho}}^{(d)}\cdots{\boldsymbol{\rho}}^{(2)}$ computes the parity of a random subset $\mathbf{S}\subseteq[n]$ of coordinates (or its negation). With an appropriate choice of the $\ast$-probability $p$ we have that $|\mathbf{S}|$ is large with high probability; recall that $\pm\,\mathsf{Parity}_{k}$ (the $k$-variable parity function or its negation) has zero correlation with any decision tree of depth at most $k-1$. For the third property, we note that for all values of $p\in(0,1)$, a random restriction ${\boldsymbol{\rho}}\leftarrow\mathcal{R}(p)$ specifies a uniform random subcube of $\{0,1\}^{n}$ (of dimension $|{\boldsymbol{\rho}}^{-1}(\ast)|$). Therefore, the third property is a consequence of the simple fact that a uniform random point within a uniform random subcube is itself a uniform random point from $\{0,1\}^{n}$.

With the above framework in mind, we notice a conceptual challenge in proving $\mathsf{AC^{0}}$ depth hierarchy theorems via the random restriction method: even focusing only on the worst-case (i.e. ignoring Property 3), the random restrictions $\mathcal{R}_{k}$ will have to satisfy Properties 1 and 2 with the target function $f$ being computable in $\mathsf{AC^{0}}$. This is a significantly more delicate task than (say) proving $\mathsf{Parity}\notin\mathsf{AC^{0}}$ since, roughly speaking, in the latter case the target function $f\equiv\mathsf{Parity}$ is “much more complex” than the circuit $C\in\mathsf{AC^{0}}$ to begin with. In an $\mathsf{AC^{0}}$ depth hierarchy theorem, both the target $f$ and the approximating circuit $C$ are constant-depth circuits; the target $f$ is “more complex” than $C$ in the sense that it has larger circuit depth, but this is offset by the fact that the circuit size of $C$ is allowed to be exponentially larger than that of $f$ (as is the case in both Håstad’s and our theorem). We refer the reader to Chapter §6.2 of Hastad’s thesis [Hås86b] which contains a discussion of this very issue.

Håstad overcomes this difficulty by replacing the “standard” random restrictions $\mathcal{R}(p)$ with random restrictions specifically suited to Sipser functions being the target: his “blockwise” random restrictions are designed so that (1) they reduce the depth of the formula computing the Sipser function by one, but otherwise essentially preserve the rest of its structure, and yet (2) a switching lemma still holds for any circuit with sufficiently small bottom fan-in. These correspond to Properties 2 and 1 respectively. However, unlike $\mathcal{R}(p)$, Håstad’s blockwise random restrictions are not independent across coordinates and do not satisfy Property 3: their composition does not complete to the uniform distribution $\mathcal{U}$ (and indeed it does not complete to any product distribution). This is why Håstad’s construction establishes a worst-case rather than average-case depth hierarchy theorem.

2 Our main technique: Random projections

The crux of the difficulty in proving an average-case $\mathsf{AC^{0}}$ depth hierarchy theorem therefore lies in designing random restrictions that satisfy Properties 1, 2, and 3 simultaneously, for a target $f$ in $\mathsf{AC^{0}}$ and an arbitrary approximating circuit $C$ of smaller depth but possibly exponentially larger size. To recall, the “standard” random restrictions $\mathcal{R}(p)$ satisfy Properties 1 and 3 but not 2, and Håstad’s blockwise variant satisfies Properties 1 and 2 but not 3.

In this paper we overcome this difficulty with projections, a generalization of restrictions. Given a set of formal variables $\mathcal{X}=\{x_{1},\ldots,x_{n}\}$, a restriction $\rho$ either fixes a variable $x_{i}$ (i.e. $\rho(x_{i})\in\{0,1\}$) or keeps it alive (i.e. $\rho(x_{i})=x_{i}$, often denoted by $\ast$). A projection, on the other hand, either fixes $x_{i}$ or maps it to a variable $y_{j}$ from a possibly different space of formal variables $\mathcal{Y}=\{y_{1},\ldots,y_{n^{\prime}}\}$. Restrictions are therefore a special case of projections where $\mathcal{Y}\equiv\mathcal{X}$, and each $x_{i}$ can only be fixed or mapped to itself. (See Definition 4 for precise definitions.) Our arguments crucially employ projections in which $\mathcal{Y}$ is smaller than $\mathcal{X}$, and where moreover each $x_{i}$ is only mapped to a specific element $y_{j}$ where $j$ depends on $i$ in a carefully designed way that depends on the structure of the formula computing the Sipser function. Such “collisions”, where blocks of distinct formal variables in $\mathcal{X}$ are mapped to the same new formal variable $y_{i}\in\mathcal{Y}$, play a crucial role in our approach. (We remark that ours is not the first work to consider such a generalization of restrictions. Random projections are also used in the work of Impagliazzo and Segerlind, which establishes lower bounds against constant-depth Frege systems with counting axioms in proof complexity [IS01].)

At a high level, our overall approach is structured around a sequence $\mathbf{\Psi}$ of (adaptively chosen) random projections satisfying Properties 1, 2, and 3 simultaneously, with the target $f$ being $\mathsf{Sipser}$, a slight variant of the Sipser function which we define in Section 6. We briefly outline how we establish each of the three properties (it will be more natural for us to prove them in a slightly different order from the way they are listed in Section 4.1):

Property 3: $\mathbf{\Psi}$ completes to the uniform distribution. Like Håstad’s blockwise random restrictions (and unlike the “standard” random restrictions $\mathcal{R}(p)$), the distributions of our random projections are not independent across coordinates: they are carefully correlated in a way that depends on the structure of the formula computing $\mathsf{Sipser}$. As discussed above, there is an inherent tension between the need for such correlations on one hand (to ensure that $\mathsf{Sipser}$ “retains structure”), and the requirement that their composition completes to the uniform distribution on the other hand (to yield uniform-distribution correlation bounds). We overcome this difficulty with our notion of projections: in Section 8 we prove that the composition $\mathbf{\Psi}$ of our sequence of random projections completes to the uniform distribution (despite the fact that every one of the individual random projections comprising $\mathbf{\Psi}$ is highly-correlated among coordinates.)

Property 1: Approximator $C$ simplifies. Next we prove that approximating circuits $C$ of the types specified in our main lower bounds (Theorems 6 and 7) “collapse to a simple function” with high probability under our sequence $\mathbf{\Psi}$ of random projections. Following the standard “bottom-up” approach to proving lower bounds against small-depth circuits, we establish this by arguing that each of the individual random projections comprising $\mathbf{\Psi}$ “contributes to the simplification” of $C$ by reducing its depth by (at least) one.

More precisely, in Section 9 we prove a projection switching lemma, showing that a small-width DNF or CNF “switches” to a small-depth decision tree with high probability under our random projections. (The depth reduction of $C$ follows by applying this lemma to every one of its bottom-level depth-$2$ subcircuits.) Recall that the random projection of a depth-$2$ circuit over a set of formal variables $\mathcal{X}$ yields a function over a new set of formal variables $\mathcal{Y}$, and in our case $\mathcal{Y}$ is significantly smaller than $\mathcal{X}$. In addition to the structural simplification that results from setting variables to constants (as in Håstad’s Switching Lemma for random restrictions), the proof of our projection switching lemma also crucially exploits the additional structural simplification that results from distinct variables in $\mathcal{X}$ being mapped to the same variable in $\mathcal{Y}$.

Property 2: Target $\mathsf{Sipser}$ retains structure. Like Håstad’s blockwise random restrictions, our random projections are defined with the target function $\mathsf{Sipser}$ in mind; in particular, they are carefully designed so as to ensure that $\mathsf{Sipser}$ “retains structure” with high probability under their composition $\mathbf{\Psi}$.

In Section 10.1 we define the notion of a “typical” outcome of our random projections, and prove that with high probability all the individual projections comprising $\mathbf{\Psi}$ are typical. (Since our sequence of random projections is chosen adaptively, this requires a careful definition of typicality to facilitate an inductive argument showing that our definition “bootstraps” itself.) Next, in Section 10.2 we show that typical projections have a “very limited and well-controlled” effect on the structure of $\mathsf{Sipser}$; equivalently, $\mathsf{Sipser}$ is resilient against typical projections. Together, the results of Section 10.1 and 10.2 show that with high probability, $\mathsf{Sipser}$ reduces under $\mathbf{\Psi}$ to a “well-structured” formula, in sharp contrast with our results from Section 9 showing that the approximator “collapses to a simple function” with high probability under $\mathbf{\Psi}$.

We remark that the notion of random projections plays a key role in ensuring all three properties above. (We give a more detailed overview of our proof in Section 7.3 after setting up the necessary terminology and definitions in the next two sections.)

Preliminaries

Let $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{n}$ be independent random variables satisfying $0\leq\mathbf{Z}_{i}\leq 1$ for all $i\in[n]$. Let $\mathbf{S}=\mathbf{Z}_{1}+\cdots+\mathbf{Z}_{n}$, and $\mu=\operatorname{{\bf E}}[\mathbf{S}]$. Then for all $\gamma\geq 0$,

We will use the following fact implicitly in many of our calculations:

Finally, the following standard approximations will be useful:

and for $0\leq x\leq 1$, we have $1+x\leq e^{x}\leq 1+2x.$

We write $\log$ to denote logarithm base 2 and $\ln$ to denote natural log.

2 Notation

A DNF is an $\mathsf{OR}$ of $\mathsf{AND}$s (terms) and a CNF is an $\mathsf{AND}$ of $\mathsf{OR}$s (clauses). The width of a DNF (respectively, CNF) is the maximum number of variables that occur in any one of its terms (respectively, clauses). We will assume throughout that our circuits are alternating, meaning that every root-to-leaf path alternates between $\mathsf{AND}$ gates and $\mathsf{OR}$ gates, and layered, meaning that for every gate $\mathsf{G}$, every root-to-G path has the same length. By a standard conversion, every depth-$d$ circuit is equivalent to a depth-$d$ alternating layered circuit with only a modest increase in size (which is negligible given the slack on our analysis). The size of a circuit is its number of gates, and the depth of a circuit is the length of its longest root-to-leaf path.

For $p\in$ and symbols $\bullet,\circ$, we write “$\{\bullet_{p},\circ_{1-p}\}$” to denote the distribution over $\{\bullet,\circ\}$ which outputs $\bullet$ with probability $p$ and $\circ$ with probability $1-p.$ We write “$\,\{\bullet_{p},\circ_{1-p}\}^{k}\,$” to denote the product distribution over $\{\bullet,\circ\}^{k}$ in which each coordinate is distributed independently according to $\{\bullet_{p},\circ_{1-p}\}$. We write “ $\{\bullet_{p},\circ_{1-p}\}^{k}\setminus\{\bullet\}^{k}$ ” to denote the product distribution conditioned on not outputting $\{\bullet\}^{k}$.

Throughout the paper we use boldfaced characters such as ${\boldsymbol{\rho}}$, $\mathbf{X}$, etc. to denote random variables. We write “$a=b\pm c$” as shorthand to denote that $a\in[b-c,b+c]$, and similarly $a\neq b\pm c$ to denote that $a\notin[b-c,b+c]$. For a positive integer $k$ we write “$[k]$” to denote the set $\{1,\dots,k\}.$

The bias of a Boolean function $f$ under an input distribution $\mathbf{Z}$ is defined as

3 Restrictions and random restrictions

A restriction $\rho$ of a finite base set $\{x_{\alpha}\}_{\alpha\in\Omega}$ of Boolean variables is a string $\rho\in\{0,1,\ast\}^{\Omega}$. (We sometimes equivalently view a restriction $\rho$ as a function $\rho:\Omega\to\{0,1,\ast\}.$) Given a function $f:\{0,1\}^{\Omega}\to\{0,1\}$ and restriction $\rho\in\{0,1,\ast\}^{\Omega}$, the $\rho$-restriction of $f$ is the function $(f\upharpoonright\rho):\{0,1\}^{\Omega}\to\{0,1\}$ where

Given a distribution $\mathcal{R}$ over restrictions $\{0,1,\ast\}^{\Omega}$ the $\mathcal{R}$-random restriction of $f$ is the random function $f\upharpoonright{\boldsymbol{\rho}}$ where ${\boldsymbol{\rho}}\leftarrow\mathcal{R}$.

Let $\rho,\tau\in\{0,1,\ast\}^{\Omega}$ be two restrictions. We say that $\tau$ is a refinement of $\rho$ if $\rho^{-1}(1)\subseteq\tau^{-1}(1)$ and $\rho^{-1}(0)\subseteq\tau^{-1}(0)$, i.e. every variable $x_{\alpha}$ that is set to 0 or 1 by $\rho$ is set in the same way by $\tau$ (and $\tau$ may set additional variables to 0 or 1 that $\rho$ does not set).

Let $\rho,\rho^{\prime}\in\{0,1,\ast\}^{\Omega}$ be two restrictions. Their composition, denoted $\rho\rho^{\prime}\in\{0,1,\ast\}^{\Omega}$, is the restriction defined by

Note that $\rho\rho^{\prime}$ is a refinement of $\rho$.

4 Projections and random projections

The 𝖲𝗂𝗉𝗌𝖾𝗋𝖲𝗂𝗉𝗌𝖾𝗋\mathsf{Sipser} function and its basic properties

Every leaf of $\mathsf{Sipser}_{d}$ occurs at the same depth (distance from the root) $d$; there are exactly $n$ leaves ($n$ will be defined below) and each variable occurs at precisely one leaf. The formula is alternating, meaning that every root-to-leaf path alternates between $\mathsf{AND}$ gates and $\mathsf{OR}$ gates; all of the gates that are adjacent to input variables (i.e. the depth-$(d-1)$ gates) are $\mathsf{AND}$ gates, so the root is an $\mathsf{OR}$ gate if $d$ is even and is an $\mathsf{AND}$ gate if $d$ is odd. The formula is also depth-regular, meaning that for each depth (distance from the root) $0\leq k\leq d-1$, all of the depth-$k$ gates have the same fan-in. Hence to completely specify the $\mathsf{Sipser}_{d}$ formula it remains only to specify the fan-in sequence $w_{0},\dots,w_{d-1}$, where $w_{k}$ is the fan-in of every gate at depth $k$. These fan-ins are as follows:

and we observe that $p$ is the probability that a depth-$(d-1)$ $\mathsf{AND}$ gate is satisfied by a uniform random choice of $\mathbf{X}\leftarrow\{0_{1/2},1_{1/2}\}^{n}$.

For each value $1\leq k\leq d-2$, the value of $w_{k}$ is $w_{k}=w$ where

where $t_{1}$ and $q$ will be defined in Section 7.1, see specifically Equations (8) and (7). Roughly speaking, $w_{0}$ is chosen so that the overall formula is essentially balanced under the uniform distribution (i.e. $\mathsf{Sipser}_{d}$ satisfies (6) below); see (9) and the discussion thereafter.

The number of input variables $n$ for $\mathsf{Sipser}_{d}$ is $n=\prod_{k=0}^{d-1}w_{k}=w^{d-2}w_{d-1}w_{0}$. The estimates for $t_{1}$ and $q$ given in (10) imply that $w_{0}=2^{m}\ln(2)\cdot(1\pm o_{m}(1))$, so we have that

We note that for the range of values $2\leq d\leq{\frac{c\sqrt{\log n}}{\log\log n}}$ that we consider in this paper, a direct (but somewhat tedious) analysis implies that the $\mathsf{Sipser}_{d}$ function is indeed essentially balanced, or more precisely, that it satisfies

However, since this fact is a direct byproduct of our main theorem (which shows that $\mathsf{Sipser}_{d}$ cannot be $(1/2-o_{n}(1))$-approximated by any depth-$(d-1)$ formula, let alone by a constant function), we omit the tedious direct analysis here.

We specify an addressing scheme for the gates and input variables of our $\mathsf{Sipser}_{d}$ formula which will be heavily used throughout the paper. Let $A_{0}=\{\mathsf{output}\}$, and for $1\leq k\leq d$, let $A_{k}=A_{k-1}\times[w_{k-1}]$. An element of $A_{k}$ specifies the address of a gate at depth (distance from the output node) $k$ in $\mathsf{Sipser}_{d}$ in the obvious way; so $A_{d}=\{{\mathsf{output}}\}\times[w_{0}]\times\cdots\times[w_{d-1}]$ is the set of addresses of the input variables and $|A_{d}|=n$.

We close this section by introducing notation for the following family of formulas related to $\mathsf{Sipser}_{d}$:

For $1\leq k\leq d$, we write $\mathsf{Sipser}_{d}^{(k)}:\{0,1\}^{A_{k}}\to\{0,1\}$ to denote the depth-$k$ formula obtained from $\mathsf{Sipser}_{d}$ by discarding all gates at depths $k+1$ through $d-1$, and replacing every depth-$k$ gate at address $a\in A_{k}$ with a fresh formal variable $y_{a}$.

Note that $\mathsf{Sipser}^{(1)}_{d}$ is the top gate of $\mathsf{Sipser}_{d}$; in particular, $\mathsf{Sipser}^{(1)}_{d}$ is an $w_{0}$-way $\mathsf{OR}$ if $d$ is even, and an $w_{0}$-way $\mathsf{AND}$ if $d$ is odd. Note also that $\mathsf{Sipser}_{d}^{(d)}$ is simply $\mathsf{Sipser}_{d}$ itself, although we stress that $\mathsf{Sipser}^{(k)}_{d}$ is not the same as $\mathsf{Sipser}_{k}$ for $1\leq k\leq d-1$.

Setup for and overview of our proof

The starting point for our parameter settings is the pair of fixed values

Given these fixed values of $\lambda$ and $q$, we define a sequence of parameters $t_{d-1},\dots,t_{1}$ as

The next lemma gives bounds on $t_{d-1},\ldots,t_{1}$ which show that these values “stay under control”. By our definitions of $\lambda,p$ and $q$ in (7), we have that $t_{d-1}=q-o(q)$, and we will need the fact that the values of $t_{k}$ for $k=d-1,\ldots,2$ remain in the range $q\pm o(q)$. Roughly speaking, since each $t_{k-1}$ is defined inductively in terms of $t_{k}$ from $k=d-1$ down to $1$, we have to argue that these values do not “drift” significantly from the initial value of $t_{d-1}=q-o(q)$. We need to keep these values under control for two reasons: first, the magnitude of these values directly affects the strength of our Projection Switching Lemma — as we will see in Section 9.1, our error bounds depend on the magnitude of these $t_{k}$’s. Second, since the top fan-in $w_{0}$ of our $\mathsf{Sipser}_{d}$ function is directly determined by $t_{1}$ (recall (4)), we need a bound on $t_{1}$ to control the structure of this function.

There is a universal constant $c>0$ such that for $2\leq d\leq{\frac{cm}{\log m}}$, we have that $t_{k}=q\pm q^{1.1}$ for all $k\in[d-1]$.

We defer the proof of Lemma 7.1 to Appendix A. The $k=1$ case of Lemma 7.1 along with our definition of $w_{0}$ (recall (4)) give us the bounds

These bounds (showing that $(1-t_{1})^{qw_{0}}$ is very close to $1/2$) will be useful for our proof in Section 10.2 that $\mathsf{Sipser}_{d}$ remains essentially unbiased (i.e. it remains “structured”) under our random projections, which in turn implies our claim (6) that $\mathsf{Sipser}_{d}$ is essentially balanced (see Remark 17).

We close this subsection with the following estimates of our key parameters in terms of $w$ for later reference:

2 The initial and subsequent random projections

As described in Section 4, our overall approach is structured around a sequence of random projections which we will apply to both the target function $\mathsf{Sipser}_{d}$ and the approximating circuit $C$. Both are functions over $\{0,1\}^{n}\equiv\{0,1\}^{A_{d}}$, and our $d-1$ random projections will sequentially transform them from being over $\{0,1\}^{A_{k}}$ to being over $\{0,1\}^{A_{k-1}}$ for $k=d$ down to $k=1$. Thus, at the end of the overall process both the randomly projected target and the randomly projected approximator are functions over $\{0,1\}^{A_{1}}\equiv\{0,1\}^{w_{0}}$.

We now formally define this sequence of random projections; recalling Definition 4, to define a random projection operator it suffices to specify a distribution over random restrictions, and this is what we will do. We begin with the initial random projection:

Our subsequent random projections will alternate between two types, depending on whether $d-k$ is even or odd. These types are dual to each other in the sense that their distributions are completely identical, except with the roles of $1$ and swapped; in other words, the bitwise complement of a draw from the first type yields a draw from the second type. To avoid redundancy in our definitions we introduce the notation in Table 2: we represent $\{0,1\}^{A_{k}}$ as $\{\bullet,\circ\}^{A_{k}}$, where a $\circ$-value corresponds to either $1$ or depending on whether $d-k$ is even or odd, and the $\bullet$-value is simply the complement of the $\circ$-value. For example, the string $(\circ,\circ,\bullet,\circ)$ translates to $(1,1,0,1)$ if $d-k$ is even, and $(0,0,1,0)$ if $d-k$ is odd.

Let $2\leq k\leq d$ and $\tau\in\{\bullet,\circ,\ast\}^{A_{k-1}\times[w_{k-1}]}\equiv\{\bullet,\circ,\ast\}^{A_{k}}$. The lift of $\tau$ is the string $\widehat{\tau}\in\{\bullet,\circ,\ast\}^{A_{k-1}}$ defined as follows: for each $a\in A_{k-1}$, the coordinate $\widehat{\tau}_{a}$ of $\widehat{\tau}$ is

We remind the reader that $\tau\in\{\bullet,\circ,\ast\}^{A_{k}}$ and $\widehat{\tau}\in\{\bullet,\circ,\ast\}^{A_{k-1}}$ belong to adjacent levels (i.e. they fall under different rows in Table 2). Consequently, for example, if $1$ corresponds to $\bullet$ as a symbol in $\tau$ then it corresponds to $\circ$ as a symbol in $\widehat{\tau}$, and vice versa.

Later this notion of the “lift” of a restriction will also be handy when we describe the effect of our random projections on the target function $\mathsf{Sipser}_{d}$. The high-level rationale behind it is that $\widehat{\tau}\in\{\bullet,\circ,\ast\}^{A_{k-1}}$ denotes the values that the bottom-layer gates of $\mathsf{Sipser}^{(k)}_{d}$ take on when its input variables are set according to $\tau\in\{\bullet,\circ,\ast\}^{A_{k}}$. As a concrete example, suppose $d-k\equiv 0\mod 2$ and let $\tau\in\{0,1,\ast\}^{A_{k}}$ be a restriction. Since $d-k\equiv 0\mod 2$, recalling Table 2 we have that the bottom-layer gates of $\mathsf{Sipser}^{(k)}_{d}$ (or equivalently, the gates of $\mathsf{Sipser}_{d}$ at depth $k-1$) are $\mathsf{AND}$ gates. For every block $a\in A_{k-1}$,

If $\tau_{a,i}=0$ for some $i\in[w_{k-1}]$, the $\mathsf{AND}$ gate at address $a$ is falsified and has value .

If $\tau_{a,i}=\{1\}^{w_{k-1}}$, the $\mathsf{AND}$ gate at address $a$ is satisfied and has value $1$.

If $\tau_{a}\in\{\ast,1\}\setminus\{1\}^{w_{k-1}}$, the value of the $\mathsf{AND}$ gate at address $a$ remains undetermined (which we denote as having value $\ast$).

These three cases correspond exactly to the three branches in Definition 7, and so indeed $\widehat{\tau}_{a}\in\{0,1,\ast\}$ represents the value that the $\mathsf{AND}$ gate at address $a$ takes when its input variables are set according to $\tau_{a}\in\{0,1,\ast\}^{w_{k-1}}$.

We shall require the following technical definition:

For $2\leq k\leq d-1$ and a set $S\subseteq[w_{k-1}]$, we say that $S$ is $k$-acceptable if

For intuition, in the above definition $S$ should be thought of as specifying those children of a particular depth-$(k-1)$ gate of $\mathsf{Sipser}_{d}$ that take the value $\ast$ under certain restrictions (defined below). We want the size of this set to be essentially $qw$, and as $k$ gets smaller (closer to the root), for technical reasons we allow more and more — but never too much — deviation from this desired value. See Section 10.1 for a detailed discussion.

We are now ready to give the key definition for our subsequent random projections:

Let $\tau\in\{\bullet,\circ,\ast\}^{A_{k}}$ where $2\leq k\leq d-1$. We define a distribution $\mathcal{R}(\tau)$ over refinements ${\boldsymbol{\rho}}\in\{\bullet,\circ,\ast\}^{A_{k}}$ of $\tau$ as follows. Independently for each $a\in A_{k-1}$, writing $S_{a}=S_{a}(\tau)$ to denote $\tau_{a}^{-1}(\ast)=\{i\in[w_{k-1}]\colon\tau_{a,i}=\ast\}$ and ${\boldsymbol{\rho}}(S_{a})$ to denote the substring of ${\boldsymbol{\rho}}_{a}$ with coordinates in $S_{a}$,

If $\widehat{\tau}_{a}=\circ$ (i.e. if $\tau_{a,i}=\bullet$ for some $i\in[w_{k-1}]$) or if $S_{a}$ is not $k$-acceptable, then

If $\widehat{\tau}_{a}=\ast$ (i.e. if $\tau_{a,i}\in\{\ast,\circ\}^{w_{k-1}}\setminus\{\circ\}^{w_{k-1}}$) and $S_{a}$ is $k$-acceptable, then

(Note that if $\widehat{\tau}_{a}=\bullet$ then $\tau_{a,i}=\circ$ for all $i\in[w_{k-1}]$, and so $\tau_{a}$ cannot be refined further.)

For all $a\in A_{k-1}$ and $i\in[w_{k-1}]$ such that $\tau_{a,i}\in\{\bullet,\circ\}$, we set ${\boldsymbol{\rho}}_{a,i}=\tau_{a,i}$ and so ${\boldsymbol{\rho}}$ is indeed a refinement of $\tau$.

We remark that $q_{a}$ as defined in (13) is indeed a well-defined quantity in $$if$S_{a}$is$k$-acceptable. We omit the straightforward verification here since our analysis in Section 10.1 will in fact establish a stronger statement showing that$q_{a}=q\pm o(q)$; see Lemma 10.5.

3 Overview of our proof

With the definitions from Section 7.2 in hand, we are (finally) in a position to give a detailed overview of our proof. Let $C$ be a depth-$d$ approximating circuit for $\mathsf{Sipser}_{d}$, where $C$ either has significantly smaller bottom fan-in than $\mathsf{Sipser}_{d}$ (in the case of Theorem 6) or the opposite alternation pattern to $\mathsf{Sipser}_{d}$ (in the case of Theorem 7), and $C$ satisfies the size bounds given in the respective theorem statements. In both cases our goal is to show that $C$ has small correlation with $\mathsf{Sipser}_{d}$, i.e. to prove that

Given a function $f:\{0,1\}^{n}\to\{0,1\}$, we write $\mathbf{\Psi}(f):\{0,1\}^{w_{0}}\to\{0,1\}$ to denote the following random projection of $f$:

Recalling the framework for proving correlation bounds discussed in Section 4, the rest of the paper is structured around showing that a $\mathbf{\Psi}$-random projection satisfies the three key properties outlined in Section 4:

The approximating circuit $C$ simplifies under a $\mathbf{\Psi}$-random projection.

The target $\mathsf{Sipser}_{d}$ remains structured under a $\mathbf{\Psi}$-random projection.

$\mathbf{\Psi}$ completes to the uniform distribution.

We begin in Section 8 with Property 3. We show that

where $\mathbf{Y}$ is drawn from an appropriate product distribution $\mathcal{D}$ over $\{0,1\}^{w_{0}}$ ($\mathcal{D}$ is the $t_{1}$-biased product distribution if $d$ is even, and $(1-t_{1})$-biased product distribution if $d$ is odd). This reduces our goal of bounding the correlation between $\mathsf{Sipser}_{d}$ and $C$ (i.e. (14)) under the uniform distribution, to the task of bounding the correlation between their $\mathbf{\Psi}$-random projections $\mathbf{\Psi}(\mathsf{Sipser}_{d})$ and $\mathbf{\Psi}(C)$ with respect to $\mathcal{D}$.

With the reduction (15) in hand, we turn our attention to Property 1, showing that the approximating circuit $C$ of the type specified in either Theorems 6 or 7 “collapses to a simple function” under a $\mathbf{\Psi}$-random projection. More precisely, for the case that the depth-$d$ circuit $C$ has significantly smaller bottom fan-in than $\mathsf{Sipser}_{d}$ we show that $C$ collapses to a shallow decision tree, and for the case that $C$ has the opposite alternation pattern to $\mathsf{Sipser}_{d}$ we show that $C$ collapses to a small-width depth-two circuit with top gate opposite to that of $\mathbf{\Psi}(\mathsf{Sipser}_{d})$. (In both cases these statements are with high probability under a $\mathbf{\Psi}$-random projection.)

if $\rho^{(k+1)}$ is typical, then ${\boldsymbol{\rho}}^{(k)}\leftarrow\mathcal{R}(\widehat{\rho^{(k+1)}})$ is also typical with high probability.

We establish (i) and (ii) in Section 10.1. Together, (i) and (ii) imply that with high probability $\mathbf{\Psi}\equiv\{{\boldsymbol{\rho}}^{(k)}\}_{k\in\{2,\ldots,d\}}$ is such that ${\boldsymbol{\rho}}^{(d)},\ldots,{\boldsymbol{\rho}}^{(2)}$ are all typical; we use this in Section 10.2.

With the notion of typical restrictions in hand, in Section 10.2 we establish Property 2 showing that $\mathsf{Sipser}_{d}$ “survives” a $\mathbf{\Psi}$-random projection (i.e. it “retains structure”) with high probability. More formally, for outcomes $\Psi\equiv\{\rho^{(k)}\}_{k\in\{2,\ldots,d\}}$ of $\mathbf{\Psi}$ such that $\rho^{(d)},\ldots,\rho^{(2)}$ are all typical, we prove that the $\Psi$-projected target $\Psi(\mathsf{Sipser}_{d})$ is “well-structured” in the following sense:

$\Psi(\mathsf{Sipser}_{d})$ is a depth-one formula: an $\mathsf{OR}$ if $d$ is even, an $\mathsf{AND}$ if $d$ is odd.

The bias of $\Psi(\mathsf{Sipser}_{d})$ under $\mathcal{D}$ is close to $1/2$; that is,

Recall that we have shown in Subsection 10.1 that with high probability $\mathbf{\Psi}\equiv\{{\boldsymbol{\rho}}^{(k)}\}_{k\in\{2,\ldots,d\}}$ is such that ${\boldsymbol{\rho}}^{(d)},\ldots,{\boldsymbol{\rho}}^{(2)}$ are all typical. Therefore, the results of these two subsections together imply that the randomly projected target $\mathbf{\Psi}(\mathsf{Sipser}_{d})$ satisfies both (i) and (ii) with high probability.