Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

Introduction

Despite considerable study in the complexity of neural networks (see Section 2 for more background), the power of a single hidden layer is still poorly understood: prior to our work, it was open whether every function in nondeterministic $2^{O(n)}$ time could be computed by ${\sf LTF}\circ{\sf LTF}$ circuit families (or ${\sf TC}^{0}_{3}$ families) with $O(n)$ gates, or by ${\sf LTF}\circ{\sf LTF}$ circuit families with $n^{3/2}\cdot\text{poly}(\log n)$ wires. (Linear-gate lower bounds were proved by several groups in the early 90’s; an $n^{3/2}$ wire lower bound was proved in 1993 by Impagliazzo, Paturi, and Saks [IPS93]. See Section 2.)

By results of Allender and Koucky [AK10], in order to separate ${\sf NC}^{1}$ from ${\sf TC}^{0}$, we only need to exhibit a function in ${\sf NC}^{1}$ that does not have $n^{1.1}$ gates for every depth $d\geq 2$. That is, the problem of proving super-linear gate lower bounds for all $O(1)$-depth threshold circuits turns out to be as difficult as proving super-polynomial lower bounds for $O(1)$-depth threshold circuits. Before we can do that, we have to first prove non-linear gate lower bounds for depth-three circuits.

We prove the first non-trivial super-linear gate lower bounds and super-quadratic wire lower bounds for depth-two threshold circuits (${\sf LTF}\circ{\sf LTF}$), and depth-three majority circuits (${\sf TC}^{0}_{3}$). Our hard functions have much lower complexity than ${\sf NTIME}[2^{O(n)}]$; they are in fact computable in ${\sf P}$ (even in uniform ${\sf TC}^{0}$ itself).

where $x\in\{0,1\}^{2^{k}}$, and $a_{i,j}\in\{0,1\}$. In words, $A_{n}$ computes the parity on $k$ disjoint sets of $2^{k}/k$ inputs, then feeds the resulting $k$-bit string to the multiplexer function on the remaining $2^{k}$ inputs $x$. (For simplicity we may think of $k$ itself as a power of two, so we do not have to worry about divisibility issues with $2^{k}/k$.)

Since 1987, the function $A_{n}$ has been a primary target for formula size lower bounds [And87, IN88, PZ93, Hås98, IMZ12]. The best known explicit size lower bounds for formulas over both the DeMorgan basis ($n^{3-o(1)}$) and the full binary basis ($n^{2-o(1)}$) are achieved by $A_{n}$. Our first result is a non-linear gate lower bound for computing $A_{n}$ with depth-two threshold circuits:

Any function $f$ that agrees with $A_{n}$ on at least a $(1/2+\epsilon)$-fraction of inputs for some $\epsilon\gg\sqrt{\log(n)/n}$ cannot be computed by ${\sf LTF}\circ{\sf LTF}$ circuits with fewer than $\Omega(\epsilon^{3}n^{3/2}/\log^{3}(n))$ gates or fewer than $\Omega(\epsilon^{3}n^{5/2}/\log^{7/2}(n))$ wires.

In contrast with these lower bounds, there are several nice (and somewhat easy) circuit constructions for computing Andreev’s function as well:

The function $A_{n}$ has (uniform) depth-3 ${\sf MAJ}\circ{\sf MAJ}\circ{\sf MAJ}$ (i.e. ${\sf TC}^{0}_{3}$) circuits of $O(n)$ gates, (uniform) ${\sf LTF}\circ{\sf LTF}$ circuits of $O(n^{3}/\log n)$ gates, parity decision trees of depth at most $\log_{2}(n)$, and (uniform) ${\sf MOD3}\circ{\sf MOD2}$ circuits of $O(n^{2})$ gates.

Hence the lower bounds of Theorem 1.1 establish several average-case complexity hierarchies in the low-depth circuit regime: for example, $A_{n}$ is computable by depth-three LTF circuits of $O(n)$ gates, but is not computable on a $1/2+\varepsilon$ fraction of inputs by depth-two LTF circuits of $\varepsilon^{3}\cdot n^{3/2-o(1)}$ gates.

As our lower bounds are average-case, we easily obtain some lower bounds on computing $A_{n}$ with distributions of ${\sf LTF}\circ{\sf LTF}$ circuits. Say that a Boolean function $f$ is computed by an $\epsilon$-Approximate Majority of ${\sf LTF}\circ{\sf LTF}$ if there is a collection ${\cal C}$ of ${\sf LTF}\circ{\sf LTF}$ circuits such that, for every input $x$, at least a $1/2+\varepsilon$ fraction of circuits in ${\cal C}$ output the value $f(x)$.

Every $\epsilon$-Approximate Majority of ${\sf LTF}\circ{\sf LTF}$ for $A_{n}$ needs at least $\Omega(\epsilon^{3}n^{3/2}/\log^{3}(n))$ gates and $\Omega(\varepsilon^{3}n^{5/2}/\log^{7/2}n)$ wires.

This is a partial step towards lower bounds for depth-three circuits composed of MAJORITY gates with negations, i.e. the class ${\sf TC}^{0}_{3}$. It follows from our distribution results that (for example) Andreev’s function has no ${\sf TC}^{0}_{3}$ circuit of $O(n^{1.1})$ gates where the output gate has fan-in $o(n^{2/15})$.

However, as stated in Theorem 1.2, Andreev’s function has $O(n)$-gate ${\sf TC}^{0}_{3}$ circuits. To obtain super-linear gate and super-quadratic wire lower bounds in the depth-three setting, we modify Andreev somewhat, defining a new explicit function $B_{n}$. Informally, $B_{n}$ has the same inputs $(x,a)$ as $A_{n}$ with $|x|=|a|$, and as before the function divides its string $a$ into groups and takes parities of each group, but $B_{n}$ also feeds $x$ into the generator matrix of an $1/\text{poly}(n)$-balanced error-correcting code (i.e. a $1/\text{poly}(n)$-biased set) before calling the multiplexer. This is similar to a function constructed by Komargodski and Raz [KR13], who also used error-correcting codes in a modification of Andreev’s function to prove average-case formula lower bounds. We let ${\sf MAJ}\circ{\sf LTF}\circ{\sf LTF}$ be the class of circuits which compute a majority value of depth-two threshold circuits.

There is no ${\sf MAJ}\circ{\sf LTF}\circ{\sf LTF}$ circuit of $o(n^{3/2}/\log^{3}n)$ gates or $o(n^{5/2}/\log^{7/2}n)$ wires that computes $B_{n}$.

Tight Results for PARITY in Depth-Two.

Finally, we illustrate the strength of our techniques by proving asymptotically tight results on approximating the PARITY function with ${\sf LTF}\circ{\sf LTF}$ circuits:

The gate complexity of ${\sf MAJ}\circ{\sf MAJ}$ circuits that agree with PARITY on $99\%$ of all $n$-bit inputs is $\Theta(\sqrt{n})$. The wire complexity is $\Theta(n^{3/2})$. The lower bounds hold even for ${\sf LTF}\circ{\sf LTF}$ circuits.

Theorem 1.4 shows that the $\Omega(n^{3/2})$ wire lower bound and $\Omega(n^{1/2})$ gate lower bound for PARITY proved by Impagliazzo, Paturi, and Saks [IPS93] are both tight in the average case.

2 Intuition

The key to our lower bounds is a new random restriction lemma for LTFs. With random restrictions, one generally studies the probability that a distribution of partial Boolean assignments to the inputs of a circuit “forces” many gates of that circuit to output a fixed value on all remaining inputs. The idea of forcing is very natural for circuits made of AND and OR gates: an AND is “forced to ” when one of its inputs is assigned , and an OR is “forced to $1$” when one of its inputs is $1$. As a result, random restrictions have been rather effective for analyzing ${\sf AC}^{0}$ circuits made out of unbounded fan-in AND and OR gates (for example [FSS84, Yao85, Hås86, Ros08]), as well as formulas over the AND/OR/NOT basis (for example [Sub61, And87, PZ93, Hås98]). Strong average-case lower bounds for ${\sf AC}^{0}$ and formula size are also known; some have only been proved very recently [AW85, KR13, IMZ12, KRT13, Hås14, RST15].

For linear threshold functions, the notion of “forcing to a constant” is more subtle. There are two ways we could conclude that a partially restricted LTF is equivalent to a constant function: either the partial Boolean assignment makes part of the LTF so large that the threshold value is achieved on all remaining inputs, or the assignment makes the LTF so small that the threshold value is never achieved. Hence a threshold function can be “forced to ” in some cases, and $1$ in other cases. Also, note that if an LTF only depends non-trivially on a single variable after a restriction (that is, no other variables can affect the output value), then the LTF gate can be removed, and replaced with a single wire coming from that single variable. We incorporate both kinds of reasoning in our arguments.

In order for our analysis to work, we need to consider random restrictions of a structured yet “adversarial” form. In particular, let $\mathcal{P}$ be an arbitrary partition of $\{1,2,\ldots,n\}$ into equal parts, and let ${\cal R}_{\cal P}$ be the distribution of random restrictions on $n$ Boolean variables which randomly fixes all but one element of each part of $\cal P$. For our applications, one should think of $\cal P$ as partitioning $[n]$ into $k$ blocks of size $n/k$ for some $k\ll n$, so that ${\cal R}_{\cal P}$ roughly corresponds to fixing all but $k$ randomly chosen variables.

Let $f:\{0,1\}^{n}\rightarrow\{0,1\}$ be a linear threshold function. Let $\cal P$ be a partition of $[n]$ into parts of equal size, and let ${\cal R}_{\cal P}$ be the distribution on restrictions $\rho:[n]\rightarrow\{0,1,\star\}$ that randomly fixes all but one element of each part of $\cal P$. Then

For example, given a partition of the inputs with at most $\sqrt{n}/1000$ parts, it is very likely that $f$ is equivalent to a constant function, when a random element of each part is left unrestricted and all other inputs are assigned to random bits.

The primary tool in our random restriction analysis is a well-known result in additive combinatorics by Littlewood and Offord [LO43, Erd45] which (tightly) upper bounds the probability (on a random Boolean assignment) that a linear function takes on a value in a given interval of length $2$. We can use this lemma to closely estimate the probability that an LTF is “forced to a constant” when some of its inputs are randomly set to or $1$. The central intuition is that a linear threshold function is not “forced to a constant” by a partial Boolean assignment precisely when the restricted part of the linear function lies in a certain integer interval, certifying that the restricted part is neither “too high” to always exceed the threshold, nor “too low” to always fail to meet the threshold. Adapting Littlewood-Offord to this event requires some care, as we need to compute probability upper bounds for (potentially) large intervals defined by the LTF.

Another key idea in our lower bound proofs is the fact that there exist relatively hard functions for low-depth threshold circuits. This is obtained by a counting argument, showing that since there are few distinct functions computed by small threshold circuits, there must be hard functions which cannot be computed by any of them (or any small group of them).

In the previous best known lower bounds on ${\sf LTF}$ circuits of depth at least two, Impagliazzo, Paturi, and Saks [IPS93] also used a random restriction method to prove their lower bounds. There are several critical differences between their approach and ours. Their main lemmas state that for any ${\sf LTF}$ circuit with $n$ variables and $\delta n$ wires, there is a variable restriction which leaves $\Omega(n/\delta^{2})$ variables unset and makes every bottom-layer gate dependent on at most one variable. First, observe that their lemmas are nontrivial only when the number of wires is $O(n^{3/2})$. Second, the proofs of their lemmas require that they pick a particular random partition of variables in which the restriction is performed; we will need to allow an adversary to control the partition in order for our analysis to work. Third, instead of insisting that every bottom-layer gate is reduced, we use Littlewood-Offord to calculate the probability that single gate is either forced to a constant (Lemma 1.1) or depends on at most one variable (Lemma 3.1). Fourth, we use our relaxed setting to incorporate strong ${\sf LTF}\circ{\sf LTF}$ lower bounds for random functions in our arguments to gain an extra linear factor in the gate and wire lower bounds (Theorem 1.1), and we add another layer of complexity to the function to insert correlation-style arguments to gain an extra layer of circuit depth (Theorem 1.3).

Preliminaries

We denote assignments to $n$ Boolean variables by functions of the form $\tau:[n]\rightarrow\{0,1\}$.

We will apply a classical result of Littlewood and Offord [LO43] which upper bounds the number of inputs to a linear function $L(x)=\sum_{i=1}^{t}a_{i}x_{i}$ so that the output lies in a given interval $I$ of length $2$. In particular, if at least $n$ of the $a_{i}$ have $|a_{i}|\geq 1$, and if $x$ is a random point in $\{-1,1\}^{t}$, then $\Pr_{x}[L(x)\in I]\leq O(\log(n)/\sqrt{n})$. The bound was later improved to $O(1/\sqrt{n})$ by Erdős [Erd45]. By scaling the length of the interval $I$, we obtain the following:

where $\in_{u}$ denotes a uniform random choice.

Start with the original lemma: assume at least $k$ of the $a_{i}$ have $|a_{i}|\geq 1$, let $I$ be an arbitrary interval of length $2$, and obtain $\Pr_{x\in\{-1,1\}^{t}}[L(x)\in I]\leq O(1/\sqrt{k})$. What follows is some simple massaging of this statement.

Constant-Depth Threshold Lower Bounds for Random Functions

Another ingredient in our main result is a threshold circuit lower bound for random functions. This follows from a counting argument via a non-trivial upper bound on the number of distinct functions computable with low-depth LTF circuits. The upper bound on the number of possible LTFs has been proved many times; the earliest reference we have found is Winder [Win60] from the 1st Annual FOCS:

The number of linear threshold functions on $n$ variables is at most $2^{O(n^{2})}$.

The $2^{O(n^{2})}$ upper bound immediately follows from Chow’s theorem (from the 2nd Annual FOCS), which characterizes linear threshold functions by their low-degree Fourier coefficients.

Every LTF $f$ on $n$ variables is uniquely determined by its $n+1$ Fourier coefficients $\hat{f}(\emptyset),\hat{f}(1),\ldots,\hat{f}(n)$.

To see why the $2^{O(n^{2})}$ upper bound follows from Theorem 2.2, observe that each Fourier coefficient of a Boolean function can take on at most $O(2^{n})$ values, because it is an expectation of a random variable taking values in $\{-1,1\}$, over a $2^{n}$ sample space. Combined with Chow’s Theorem, the number of LTFs on $n$ variables is at most $O(2^{n})^{n+1}\leq 2^{O(n^{2})}$. For a proof, see (for example) O’Donnell and Servedio [OS11], or Knuth ([Knu11], Theorem T) who states the theorem slightly differently (the language of Chow, in fact).

A considerable generalization of Winder’s theorem was given by Roychowdhury, Siu, and Orlitsky:

Let ${\cal F}=\{f_{1},\ldots,f_{s}\}$ be a fixed collection of functions of the form $f_{i}:\{0,1\}^{n}\rightarrow\{0,1\}$. Then there are at most $(2^{n}+1)^{s+1}$ distinct functions $g:\{0,1\}^{n}\rightarrow\{0,1\}$ of the form

For completeness, we give a short self-contained proof. Our proof builds on Knuth’s elegant proof of Chow’s theorem ([Knu11], Theorem T).

We claim that, if $|S(g)|=|S(h)|$ and $\Sigma(g)=\Sigma(h)$ for two LTFs $g$ and $h$ over the same functions $f_{1},\ldots,f_{s}$, then $g(f_{1},\ldots,f_{s})=h(f_{1},\ldots,f_{s})$ as Boolean functions.

Every depth-two LTF circuit of $s+1$ gates is uniquely determined by $|S(g)|\leq 2^{n}$, $\Sigma(g)$, and the $s$ LTF gates on the bottom layer. Hence there are at most $(2^{n}+1)^{s+1}$ threshold functions over $s$ given input functions.

There are at most $2^{O(n^{2}\cdot s)}$ distinct depth-two LTF circuits, since there are at most $(2^{n}+1)^{s+1}$ possible choices for the output gate, and $2^{O(n^{2}s)}$ choices for the $s$ LTFs on the bottom layer (by Theorem 2.1).

So let’s prove the claim. Suppose $g(f_{1},\ldots,f_{s})\neq h(f_{1},\ldots,f_{s})$ as Boolean functions, but $|S(g)|=|S(h)|$ and $\Sigma(g)=\Sigma(h)$. Let $\{y_{1},\ldots,y_{k}\}\subseteq\{0,1\}^{s}$ be the set of all points in the image of $(f_{1},\ldots,f_{s}):\{0,1\}^{n}\rightarrow\{0,1\}^{s}$, such that $g(y_{i})=1$ and $h(y_{i})=0$. By definition, $\{y_{1},\ldots,y_{k}\}=(S(g)\setminus S(h))$. Because $|S(g)|=|S(h)|$, there must also be exactly $k$ points $z_{1},\ldots,z_{k}$ in the image of $(f_{1},\ldots,f_{s})$ such that $g(z_{i})=0$ and $H(z_{i})=1$; we therefore have $\{z_{1},\ldots,z_{k}\}=(S(h)\setminus S(g))$.

Since $\Sigma(g)=\Sigma(h)$, the total sum of all vectors in $S(g)$ and $S(h)$ are the same, so we must have $\sum_{i=1}^{k}y_{i}=\sum_{i=1}^{k}z_{i}$, where the sum is componentwise.

Suppose the linear function of $g(y)$ has the form $\sum_{i}w_{i}y_{i}$, and threshold value $t$. Let $w=(w_{1},\ldots,w_{s})$. By our definition of $y_{i}$ and $z_{i}$, we have $\langle w,y_{i}\rangle\geq t$ and $\langle w,z_{i}\rangle<t$ for all $i$. Therefore

This is a contradiction, since $\sum_{i=1}^{k}y_{i}=\sum_{i=1}^{k}z_{i}$ and $k>0$. ∎

Combining Theorem 2.3 with a simple counting argument, we obtain:

For all sufficiently large $n$, a randomly chosen Boolean function on $n$ variables requires depth-$2$ linear threshold circuits of size at least $\Omega(2^{n}/n^{2})$, with probability $1-o(1)$.

If we choose a function $f:\{0,1\}^{n}\rightarrow\{0,1\}$ uniformly at random, the probability it has depth-$2$ threshold circuits of size $s$ is at most $2^{O(n^{2}s)}/2^{2^{n}}$, by Theorem 2.3. For $s\leq o(2^{n}/n^{2})$, this probability is $2^{o(2^{n})}/2^{n}=o(1)$.∎

By standard arguments we also have an “inapproximability” refinement of the above corollary:

For all $\epsilon\gg\sqrt{n/2^{n}}$, and all but an $\epsilon$-fraction of $n$-bit Boolean functions $f$, there is no depth-$2$ linear threshold circuit of size $s\leq o(\varepsilon^{2}\cdot 2^{n}/n^{2})$ that agrees with $f$ on more than a $(1/2+\epsilon)$-fraction of inputs.

By Theorem 2.3, the total number of functions computed by such size-$s$ depth-$2$ circuits is at most $2^{o(\epsilon^{2}2^{n})}.$ For any such circuit, it agrees with a randomly chosen $f$ on a $(1/2+\epsilon)$-fraction of inputs with probability $2^{-\Omega(\epsilon^{2}2^{n})}$, by standard Chernoff bounds. Taking a union bound over our choice of circuits, we conclude that $f$ does not agree with any size-$s$ depth-$2$ threshold circuit on a $(1/2+\epsilon)$-fraction of inputs, with probability at least $1-\epsilon$. ∎

A Short History of Low-Depth Threshold Lower Bounds.

Hajnal et al. [HMP+93] proved the first size lower bounds for ${\sf LTF}\circ{\sf LTF}$ circuits, showing that the inner product modulo 2 (a.k.a. IP2) requires $2^{\Omega(n)}$ size when the weights of each LTF are small (polynomial in the input length). This result is often cited as saying that the inner product does not have subexponential-size ${\sf MAJ}\circ{\sf MAJ}$ circuits, as MAJORITY functions can simulate LTFs with polynomial weights. Note that IP2 has ${\sf MAJ}\circ{\sf MAJ}\circ{\sf MAJ}$ circuits with $O(n)$ gates, so we cannot use IP2 in our depth-three lower bounds. Nisan [Nis94] elegantly applied communication complexity ideas to extend the exponential lower bound to ${\sf MAJ}\circ{\sf LTF}$ circuits; that is, the lower bound holds even if the weights of the LTFs on the hidden layer are arbitrary. Later, Forster et al. [FKL+01] extended the lower bound to ${\sf LTF}\circ{\sf MAJ}$ circuits, where only the middle (hidden) layer is restricted to have small weights.

In terms of lower bounds for general ${\sf LTF}\circ{\sf LTF}$ circuits, only a few results are known. Goldmann, Håstad, and Razborov [GHR92] showed that every ${\sf LTF}\circ{\sf LTF}$ circuit can be efficiently simulated by a ${\sf MAJ}\circ{\sf MAJ}\circ{\sf MAJ}$ circuit, and computing IP2 with ${\sf LTF}\circ{\sf LTF}$ requires $\Omega(n/\log n)$ gates. Groeger and G. Turán [GT91, GT93] and Roychowdhury, Orlitsky, and Siu [ROS94a] proved that IP2 has gate complexity $\Theta(n)$ for LTF circuits; their result has no depth restriction. Paturi and Saks [PS90] showed that PARITY requires $\Omega(n/\log^{2}n)$ gates for ${\sf MAJ}\circ{\sf MAJ}$ circuits. Impagliazzo, Paturi, Saks [IPS93] showed that ${\sf LTF}\circ{\sf LTF}$ circuits computing PARITY cannot have $o(n^{3/2})$ wires, nor can they have $o(n^{1/2})$ gates. (Their proof in fact gives a lower bound for all constant depths, although the bounds get smaller as the depth increases.) In the uniform setting, Allender and Koucky [AK10] have shown that for every $d$, there is an $\varepsilon\in(0,1)$ such that the SAT problem cannot be solved by LOGTIME-uniform depth-$d$ LTF circuits with $O(n^{1+\varepsilon})$ wires. Other more recent work on ${\sf LTF}\circ{\sf LTF}$ includes [AM05, HP10, HP13, IPS13, Wil14, CS15].

In all the above cases, no super-linear gate lower bounds were known, and no quadratic wire lower bounds were known, even for ${\sf LTF}\circ{\sf LTF}$. PARITY is well-known to have ${\sf MAJ}\circ{\sf MAJ}$ circuits of $O(n)$ gates, and we show in Theorem 1.4 that there are always ${\sf MAJ}\circ{\sf MAJ}$ circuits of $O(n^{1/2})$ gates and $O(n^{3/2})$ wires which agree with PARITY on $99\%$ of the inputs, so it is impossible to extend the lower bounds of [PS90, IPS93] for PARITY in the way we seek (for good reason).

Random Restrictions on Linear Threshold Functions

We are ready to give our main lemma on random restrictions to linear threshold functions. To properly state it, we need to set up some notation. Define a restriction to be a function $\rho:[n]\rightarrow\{0,1,\star\}$. (Such a function is also called a partial assignment.) If $\cal P$ is a set partition of $[n]$, we say that $\rho$ is a random restriction across $\cal P$ if $\rho$ is obtained by first uniformly randomly choosing a one element $e_{i}$ of each part of $\cal P$, then setting $\rho(e_{i})=\star$ for each $i$, and setting $\rho(j)$ randomly and independently to either or $1$ for all other $j\in[n]$.

A completion of $\rho$ is simply a function $\tau:[n]\rightarrow\{0,1\}$ such that for all $i$ such that $\rho(i)\neq\star$ we have $\tau(i)=\rho(i)$. That is, $\tau$ extends the partial assignment $\rho$ to some full assignment on all variables. We say that an LTF $f:\{0,1\}^{n}\rightarrow\{0,1\}$ is forced to a constant by restriction $\rho$ if there is a $c\in\{0,1\}$ such that for all completions $\tau$ of $\rho$, the output of $f$ on $\tau$ always equals $c$. That is, $f$ is “forced to a constant” if $\rho$ has set enough variables of $f$ that the remaining function is constant. We record the following trivial (but crucial) observation that we can simplify circuits when their gates are forced to constants:

Reminder of Lemma 1.1 Let $f:\{0,1\}^{n}\rightarrow\{0,1\}$ be a linear threshold function. Let $\cal P$ be a partition of $[n]$ into parts of equal size, and let ${\cal R}_{\cal P}$ be the distribution on restrictions $\rho:[n]\rightarrow\{0,1,\star\}$ that randomly fixes all but one element of each part of $\cal P$. Then

Observe that Lemma 1.1 is essentially tight for the MAJORITY function (the LTF with $L(x)=\sum_{i=1}^{n}x_{i}$ and $t=\lceil n/2\rceil$). In particular, if we set all but $k$ inputs of the $n$-bit MAJORITY function to uniform random values, the MAJORITY function is not forced to a constant only when the difference between the number of $1$’s and the number of ’s is within $[-k,k]$. This occurs with probability $\sim$ $k/\sqrt{n}$ for small $k$. (This is just another way of saying that the Littlewood-Offord Lemma is tight for the vector $a=(1,\ldots,1)$.)

(In the first case, $f$ is forced to ; in the second case, $f$ is forced to $1$.) Therefore, the probability that a random restriction $\rho\sim{\cal R}_{B}$ does not force $f$ to a constant is at most the probability that $L^{\prime}(x)$ lies in the interval

Note that $|I|=\sum_{i\in B}|a_{i}|$, and that we can write $I$ an a union of intervals $I_{i}$ with $|I_{i}|=|a_{i}|$. Therefore, by a union bound we have that

For all $i=1,\ldots,n$, define $k_{i}$ to be the number of $j\in[n]$ such that $|a_{i}|\geq|a_{j}|$. Observe that

Let us prove this claim. For all $i=1,\ldots,n$, define $k^{\prime}_{i}$ to be the number of $j\in[n]-B$ such that $|a_{i}|\geq|a_{j}|$. By Lemma 2.1, we have for all $i=1,\ldots,|B|$ that

Obviously, $k^{\prime}_{i}\leq k_{i}$ for all $i\in B$. To prove (3), we need an inequality in the opposite direction. We consider two cases. First, suppose there is an $i\in B$ with at least $k_{i}/2$ different $j\in B$ satisfying $k_{j}\leq k_{i}$. Then $\sum_{i\in B}1/\sqrt{k_{i}}\geq(k_{i}/2)/\sqrt{k_{i}}\gg 1$, and inequality (3) trivially holds in this case. Otherwise, for all $i\in B$, there are at most $k_{i}/2$ different $j\in B$ with $k_{j}\leq k_{i}$. By (2), this means that $|a_{i}|\leq|a_{j}|$ for at most $k_{i}/2$ different $j$’s, implying that $k_{i}\leq k^{\prime}_{i}+k_{i}/2$ for all $i\in B$. So we have $k_{i}\leq 2k_{i}^{\prime}$ for all $i\in B$, and

and the inequality (3) holds in this case as well. Therefore

where the last inequality follows by upper bounding the sum with an integral. This completes the proof.

In order to prove our wire lower bounds, we require a version of Lemma 1.1 that yields better results for thresholds that depend on relatively few inputs. Unfortunately, a threshold gate with a single input has only one wire, and yet has a $|{\cal P}|/n$ chance of not being forced to be a constant; this is too weak of a bound for us. On the other hand, we know that a gate with only one input always returns just its input or its negation. In particular, even if a gate is not set to a constant by a restriction, we can still replace it by a single wire if its output depends on only one of the remaining inputs. In terms of this event, we can prove a much better probability bound.

For a random restriction $\rho$ and LTF $f$, we say that $f(x_{1},\ldots,x_{n})$ is forced to a function of a single input by $\rho$ if there is an $i\in[n]$ such that for all completions $\tau$ of $\rho$, the output of $f$ on $\tau$ depends only on the variable $x_{i}$ or is a fixed constant.

Let $f:\{0,1\}^{n}\rightarrow\{0,1\}$ be a linear threshold function that depends on only $w$ of its inputs. Let $\cal P$ be a partition of $[n]$ into parts of equal size, and let ${\cal R}_{\cal P}$ be the distribution on restrictions $\rho:[n]\rightarrow\{0,1,\star\}$ that randomly fixes all but one element of each part of $\cal P$. Then

Let $S$ be the set of inputs on which $f$ depends. Define $k_{i}$ for $i\in S$ as in the proof of Lemma 1.1. Suppose we have a random restriction $\rho$ that fixes all input variables except those in $B\subset[n]$.

We want to upper bound the probability that $\rho$ does not fix $f$ to a function of a single input. In order for this to happen it must be that $|B\cap S|\geq 2$, for otherwise the restriction of $f$ depends only on the coordinates in $S\cap B$. Furthermore, this event happens with probability at most $\sum_{i\in B\cap S}O(1/\sqrt{k_{i}})$, by Equation (3). Therefore, the probability that $f$ is not fixed to a function of a single input is

Tight Upper and Lower Bounds for Approximately Computing PARITY

We begin with the upper and lower bounds for computing PARITY with ${\sf LTF}\circ{\sf LTF}$ circuits, since the lower bounds here are the easiest example of what our Random Restriction Lemmas can do.

Reminder of Theorem 1.4 The gate complexity of ${\sf MAJ}\circ{\sf MAJ}$ circuits that agree with PARITY on $99\%$ of all $n$-bit inputs is $\Theta(\sqrt{n})$. The wire complexity is $\Theta(n^{3/2})$. The lower bounds hold even for ${\sf LTF}\circ{\sf LTF}$ circuits.

(Upper bound) We produce an explicit construction. Let $L_{k}=\llbracket\sum_{i=1}^{n}x_{i}\geq k\rrbracket$ be the output of a “threshold-at-least-$k$” gate over its $n$ inputs. Observe that $L_{k}-L_{k+1}$ is the 0/1 indicator function of the exact threshold function $\sum_{i=1}^{n}x_{i}=k$.

Let $c>0$ be sufficiently large in the following. We construct the top gate of our depth-two circuit to compute the threshold function defined by

This function agrees with parity as long as $n/2-c\sqrt{n}\leq\sum_{i=1}^{n}x_{i}\leq n/2+c\sqrt{n}$, and for a sufficiently large $c>0$, this happens on $99\%$ of all inputs. This circuit obviously uses $O(\sqrt{n})$ gates and $O(n^{3/2})$ wires.

(Lower Bound) We begin with the observation (originally due to Minsky and Papert [MP69]) that a single ${\sf LTF}$ with two inputs cannot approximate PARITY on more than $75\%$ of its inputs. Therefore, for every ${\sf LTF}\circ{\sf LTF}$ circuit $C$ that approximates PARITY on $99\%$ of all $n$-bit inputs, if $C$ is randomly restricted on all but two unassigned inputs, then the restricted circuit ${C}^{\prime}$ cannot be equivalent to a single ${\sf LTF}$ with more than $10\%$ probability. On the other hand, the circuit ${C}^{\prime}$ will be equivalent to a single ${\sf LTF}$ gate, unless at least one of the bottom level gates of ${C}^{\prime}$ is not forced to a function on one input: that is, at least one gate on the bottom layer is neither a projection of one input, nor is it a constant function. Call a gate “trivial” if is forced to a function on one input. Observe that a trivial gate can always be replaced by a single wire, or a constant.

So let $C$ be a depth-$2$ ${\sf LTF}$ circuit with $s$ gates and $w$ wires that agrees with PARITY on at least $99\%$ of the $n$-bit inputs. Let ${\cal P}$ be a partition of $[n]$ into two equally sized subsets. Suppose we choose a random restriction $\rho$ from ${\cal R}_{\cal P}$ on the inputs of $C$, resulting in a restricted circuit $C^{\prime}$ on two inputs. Our Random Restriction Lemmas 1.1 and 3.1 show that the number of non-trivial bottom level gates of $C$ is, in expectation,

If either $s\ll\sqrt{n}$ or $w\ll n^{3/2}$, then by Markov’s inequality, there are no non-trivial gates on the bottom layer with probability at least $50\%$. That is, on at least half of the possible random restrictions, the remaining circuit $C^{\prime}$ on two inputs is equivalent to a single ${\sf LTF}$ gate, and hence $C^{\prime}$ does not compute PARITY correctly on more than $75\%$ of its inputs. By the previous paragraph, it follows that $C$ does not compute PARITY correctly on $99\%$ of the inputs. ∎

Depth-Two Lower Bounds for the Andreev Function

The strategy for our depth-two lower bounds for $A_{n}$ has a similar structure to the known Boolean formula lower bound proofs for $A_{n}$: hit the function $A_{n}$ (and a circuit $C$ that supposedly computes it) with a random restriction of an appropriately controlled form, so that the $2^{k}$-bit input $x$ of $A_{n}$ is assigned a uniform random value, and from each block $i$ there is one $a_{i,j}$ that is left unset. The remainder implements a function on $k$ bits, whose truth table is given by $x$. When $x$ is chosen uniformly at random, we are implementing a random $k$-bit function and can use our depth-two lower bounds for random functions (Corollaries 2.1 and 2.2) to argue that the number of gates left in $C$ must be somewhat large: at least $\Omega(2^{k}/k^{2})=\Omega(n/\log^{2}n)$. However, if the original $C$ began with a small enough number of gates, the Random Restriction Lemmas tell us that we should expect the random restriction to $C$ to force many bottom-layer gates to constants (and kill many wires in $C$). Setting the parameters appropriately yields a contradiction.

Reminder of Theorem 1.1 Any function $f$ that agrees with $A_{n}$ on at least a $(1/2+\epsilon)$-fraction of inputs for some $\epsilon\gg\sqrt{\log(n)/n}$ cannot be computed by ${\sf LTF}\circ{\sf LTF}$ circuits with fewer than $\Omega(\epsilon^{3}n^{3/2}/\log^{3}(n))$ gates or fewer than $\Omega(\epsilon^{3}n^{5/2}/\log^{7/2}(n))$ wires.

Recall that $A_{n}$ has inputs $x\in\{0,1\}^{n/2}$, and $a_{i,j}\in\{0,1\}$, with $i=1,\ldots,k$ and $j=1,\ldots,2^{k}/k$, where $k:=\lfloor\log_{2}(n)\rfloor$. Let $C$ be a ${\sf LTF}\circ{\sf LTF}$ circuit with $s\leq c\epsilon^{3}n^{3/2}/\log^{3}(n)$ gates or fewer than $w\leq c\epsilon^{3}n^{5/2}/\log^{7/2}(n)$ wires for a sufficiently small constant $c>0$. By Corollary 2.2 there exists a $c^{\prime}>0$ so that with probability at least $1-\epsilon/3$ a random function $f$ on $\lfloor\log_{2}(n/2)\rfloor$ bits does not agree on a $(1/2+\epsilon/3)$-fraction of inputs with any ${\sf LTF}\circ{\sf LTF}$ circuit with fewer than $c^{\prime}\epsilon^{2}n/\log^{2}(n)$ bottom level gates. We claim that if a random choice of $x$ corresponds to the truth table of such a function $f$ (and it will, with probability at least $1-\epsilon/3$), then the probability over the remaining bits that $C$ agrees with $A_{n}$ is at most $1/2+2\epsilon/3$.

Consider fixing the bits of input to the coordinates corresponding to $x$ to such an $f$. Let $\cal P$ be the partition of the remaining $n/2$ bits of input into the $k$ subsets $\{a_{i,1},a_{i,2},\ldots,a_{i,2^{k}/k}\}$. Let $\rho$ be a random restriction from ${\cal R}_{\cal P}$. By Lemmas 1.1 and 3.1, every linear threshold function $g$ on $n/2$ bits is forced to a constant by $\rho$ with probability at least $1-O(|{\cal P}|/\sqrt{n})=1-O(\log(n)/\sqrt{n})$ and every gate with $u$ wires is forced to a function of a single input with probability at least $1-O(u|{\cal P}|^{3/2}/n^{3/2})=1-O(u\log^{3/2}(n)/n^{3/2})$. Therefore, in either case, the expected number of bottom level gates in $C$ not forced to constants by $\rho$ is at most most $c^{\prime}\epsilon^{3}n/(3\log^{2}(n))$ (assuming $c$ was sufficiently small).

Therefore, by Markov’s inequality, with probability at least $1-\epsilon/3$ we have that when $C$ is restricted by $\rho$, all but $c^{\prime}\epsilon^{2}n/\log^{2}(n)$ of the bottom level gates of $C$ are forced to functions of single inputs. In this case, $C$ is equivalent to a ${\sf LTF}\circ{\sf LTF}$ circuit with at most $c^{\prime}\epsilon^{2}n/\log^{2}(n)$ gates. On the other hand, the restriction of $A_{n}$ to $\rho$ is merely the function $f(y_{1},y_{2},\ldots,y_{k})$, where each $(y_{i}=\sum_{j}a_{i,j}\bmod 2)$ equals either one of the $k$ unassigned variables, or its negation. (Note that negations of variables cannot change the circuit size: negations can easily be accommodated in the threshold gates.) Since by assumption the function $f$ does not agree with any ${\sf LTF}\circ{\sf LTF}$ of size $c^{\prime}\epsilon^{2}n/\log^{2}(n)$ on more than a $(1/2+\epsilon/3)$-fraction of inputs, we find for those values of $f$ and $\rho$ that

From the above lower bounds, it is straightforward to conclude depth-three lower bounds for Andreev’s function with an Approximate Majority gate at the top.

Say that a Boolean function $f$ is computed by an $\epsilon$-Approximate Majority of ${\sf LTF}\circ{\sf LTF}$ if there is a collection of ${\sf LTF}\circ{\sf LTF}$ circuits such that, for every input $x$, at least a $1/2+\varepsilon$ fraction of circuits in the collection output the value $f(x)$. The following is an easy corollary of our depth-two threshold lower bounds for Andreev’s function:

Reminder of Corollary 1.1 Every $\epsilon$-Approximate Majority of ${\sf LTF}\circ{\sf LTF}$ for $A_{n}$ needs at least $\Omega(\epsilon^{3}n^{3/2}/\log^{3}(n))$ gates and $\Omega(\varepsilon^{3}n^{5/2}/\log^{7/2}n)$ wires.

Let ${\cal C}=\{C_{1},\ldots,C_{t}\}$ be a collection of ${\sf LTF}\circ{\sf LTF}$ circuits such that on every input $x$, at least $(1/2+\varepsilon)t$ of the circuits in ${\cal C}$ agree with Andreev’s function on $x$. Assuming the entire collection ${\cal C}$ has $o(\epsilon^{3}n^{3/2}/\log^{3}(n))$ total gates, it follows that every $C_{i}$ has $o(\epsilon^{3}n^{3/2}/\log^{3}(n))$ gates (we cannot expect to do much better here, since the $C_{i}$’s could share almost all of their gates and wires). Let $x_{1},\ldots,x_{2^{n}}$ be a list of all $n$-bit strings, and form a $t\times 2^{n}$ Boolean matrix $M$ where $M(i,j)=1$ if and only if $C_{i}(x_{j})$ equals Andreev’s function on $x$. By Theorem 1.1, each row of $M$ contains less than a $(1/2+\varepsilon)$-fraction of ones, so the entire matrix has less than a $(1/2+\varepsilon)$-fraction of ones. However, every column of $M$ contains at least a $(1/2+\varepsilon)$-fraction of ones, because for every input $x$, at least $(1/2+\varepsilon)$ of the circuits in ${\cal C}$ correctly compute Andreev’s function on $x$. It follows that the entire matrix has at least a $(1/2+\varepsilon)$-fraction of ones; this is a contradiction. An analogous argument works for wires, too. ∎

It follows (for example) that Andreev’s function has no ${\sf TC}^{0}_{3}$ circuit of $O(n^{1.1})$ gates where the output gate has fan-in $o(n^{2/15})$.

2 Small Circuits for Andreev’s Function

We cannot expect to prove much stronger lower bounds for $A_{n}$, as there are nice circuit constructions for the function. In particular, we cannot hope to achieve super-linear gate lower bounds for ${\sf TC}^{0}_{3}$ using $A_{n}$:

Reminder of Theorem 1.2 The function $A_{n}$ has (uniform) depth-3 ${\sf TC}^{0}$ circuits of $O(n)$ gatesRecall that a ${\sf TC}^{0}$ circuit is composed of MAJORITY gates with negations., (uniform) ${\sf LTF}\circ{\sf LTF}$ circuits of $O(n^{3}/\log n)$ gates, parity decision trees of depth at most $\log_{2}(n)$, and (uniform) ${\sf MOD3}\circ{\sf MOD2}$ circuits of size $O(n^{2})$.

(Sketch) In all below constructions, we use the fact that Andreev’s function $A_{n}$ can be represented straightforwardly as an OR of $n/2$ ANDs of $O(\log n)$ parities over $O(n/\log n)$ variables, where over the entire circuit there are only $O(\log n)$ total parity gates.

1. First, since MAJORITY (a.k.a. MAJ) can simulate AND, we can replace the OR of AND part in the above circuit for $A_{n}$ with an OR of MAJ; this part has $O(n)$ gates. Each of the $O(\log n)$ different parity functions on $O(n/\log n)$ variables can be computed with a ${\sf LTF}\circ{\sf MAJ}$ circuit of $O(n/\log n)$ gates, where the weights of the LTF gate are at most polynomial in $n$, and the sum computed in the top LTF gate always equals either $1$ or $-1$ (indeed, this is true for any symmetric function; see Proposition 1 in [HMP+93]). Given that these LTFs have this property, we can simply “merge” the top part computing an OR-MAJ with the $O(\log n)$ ${\sf LTF}\circ{\sf MAJ}$ circuits computing the bottom part, resulting in an OR of ${\sf MAJ}\circ{\sf MAJ}$ circuit of $O(n)$ total gates.

2. Each of the $O(\log n)$-fan-in ANDs in the above circuit for $A_{n}$ can be computed by a weighted sum of $n$ parities, using the Fourier representation of the $O(\log n)$-bit AND function. The OR of $O(n)$ of these weighted sums can be easily written as an LTF of $O(n^{2}/\log n)$ parities on $O(n)$ variables. From the previous paragraph, each of these parities can replaced by an ${\sf LTF}\circ{\sf LTF}$ circuit of $O(n)$ gates. The sums computed in the top LTF gates are either $1$ or $-1$, so these outputs can be composed with the top LTF gate (as in part 1), resulting in an ${\sf LTF}\circ{\sf LTF}$ circuit of $O(n^{3}/\log n)$ gates.

3. In $\log_{2}(n/2)$ depth (and $n/2$ leaves), we can compute each of the $\log_{2}(n/2)$ parities of $A_{n}$ one by one, then output the appropriate bit of the multiplexer function with one more layer of depth.

Depth-Three Lower Bounds

We now turn to proving lower bounds against ${\sf MAJ}\circ{\sf LTF}\circ{\sf LTF}$ circuits computing an explicit function. We begin with the observation that an $s(n)$-size ${\sf MAJ}\circ{\sf LTF}\circ{\sf LTF}$ circuit necessarily has $\Omega(1/s(n))$ correlation with at least one of the ${\sf LTF}\circ{\sf LTF}$ subcircuits. Therefore, it would suffice to find a function which is not $(1/2+1/\text{poly}(n))$-approximable by ${\sf LTF}\circ{\sf LTF}$ circuits of small size. Unfortunately, Andreev’s function is not sufficient for these purposes; it has correlation $\Omega(1/\sqrt{n})$ with the majority over the bits corresponding to $x$; the problem is essentially that typical $\log_{2}(n)$-bit functions have correlations on the order of $1/\sqrt{n}$ with each other. (This is of course to be expected, since Andreev is in linear-size ${\sf TC}^{0}_{3}$.)

To overcome this issue, we need to change our hard function. We have to use the $n/2$ bits $x$ of $A_{n}$ to encode a set of functions on more than $\log_{2}(n)$ bits that all have low correlation with each other. We will make use of the following construction:

Alon et al. ([AGHP92], Section 4) show how to efficiently construct an $(\varepsilon^{\prime})$-biased set $S\subseteq\{0,1\}^{t}$ such that $|S|=ct^{2}/(\varepsilon^{\prime})^{2}$ for some constant $c>0$. Setting $m=ct^{2}/(\varepsilon^{\prime})^{2}$ means that $\varepsilon^{\prime}=\sqrt{c}t/\sqrt{m}$; we will set $\varepsilon=\varepsilon^{\prime}/\sqrt{c}$. The $(\varepsilon^{\prime})$-biased property means that for every non-zero vector $v\in\{0,1\}^{t}$,

Let $m$ be a power of two, and let $n\leq\sqrt{m}$ be a positive integer. There is a function $F:\{0,1\}^{\log_{2}(m)}\times\{0,1\}^{n}\rightarrow\{0,1\}$ computable in time $\text{poly}(m,n)$ so that for any strings $x,y\in\{0,1\}^{n}$ with $x\neq y$ we have $F(z,x)=F(z,y)$ for a $(1/2+O(\epsilon))$-fraction of $\log_{2}(m)$-bit strings $z$, where $\epsilon=n/\sqrt{m}.$