Beyond the Square-Root Exponent for Depth-Three Boolean Circuits

Introduction

We study depth-three Boolean OR–AND–OR circuits with arbitrary fan-in and fan-out. Such a circuit is a disjunction of CNFs: conjunctions of clauses, each a disjunction of literals. Classical lower bounds for explicit functions have an exponent proportional to the square root of the input length. We ask whether one polynomial-time language can require more than $2^{A\sqrt{n}}$ gates for every constant $A > 0$, at every sufficiently large length. The word “one” matters: the language and its membership algorithm must be fixed before $A$ is chosen.

Throughout the paper, $S_3(f)$ denotes the minimum total number of AND and OR gates in an OR–AND–OR circuit computing $f$ exactly. Every bottom gate and the output gate are counted. Input negations are free. The three layers are successive: bottom gates read literals and optional constants, middle gates read bottom outputs, and the top gate reads middle outputs. Unary gates allow smaller-depth functions in this model.

Theorem 1.1. There is a language $L \subset\{0,1\}^*$, a deterministic Turing machine deciding $L$, and fixed positive integers $C,a$ such that the machine runs in time at most $C(n+1)^a$ on every input of length $n$. If $f_n$ is the membership function of $L$ on $\{0,1\}^n$, then

Equivalently, for every real $A > 0$, there is an integer $N_A$ such that

No uniformity or bottom fan-in restriction is imposed on the circuits.

The square-root exponent. Håstad’s random-restriction and switching method gives the $2^{\Omega(\sqrt{n})}$ depth-three lower bound for parity [6], Theorem 1. Håstad, Jukna, and Pudlák developed a top-down approach and improved the constants for parity and majority [7], Theorems 3.3 and 3.5. Paturi, Pudlák, and Zane then obtained the sharp parity bound $\Omega(n^{1/4}2^{\sqrt{n}})$ through their satisfiability coding lemma, matching the upper bound within a constant factor [11], Theorem 6. Thus parity itself cannot witness the improvement sought here. A further connection between satisfiability algorithms and isolated solutions led Paturi, Pudlák, Saks, and Zane to a code-membership lower bound with leading exponent $(\pi/\sqrt{6})\sqrt{n}$, under their stated code-parameter conditions [10], Theorem 6. These bounds remain at the constant-times-square-root scale.

Theorem 1.1 makes the ratio of the exponent to $\sqrt{n}$ unbounded. This is the depth-three lower-bound problem discussed by Gurumukhani, Paturi, Pudlák, Saks, and Talebanfard [5], Section 1.1 and still identified as open in [4], Section 1. It is weaker than a lower bound $2^{n^{1/2+\varepsilon}}$ for a fixed $\varepsilon> 0$, the question raised in [7], Section 5, Problem 2. The depth remains three throughout.

Bounds for restricted bottom fan-in have a different scale. Paturi, Saks, and Zane constructed logspace-uniform NC$^1$ functions with $2^{n-o(n)}$ gate lower bounds when bottom fan-in is at most two [12], Corollary 5.4. Gurumukhani, Paturi, Pudlák, Saks, and Talebanfard connected local enumeration algorithms to majority lower bounds and obtained an exponential bound for bottom fan-in three [5], Proposition 3 and Corollary 5. In such bounded-width models, counting the middle CNFs can be useful. For arbitrary bottom fan-in, that count alone cannot measure complexity: every Boolean function has a representation by a single CNF. The total gate count in Theorem 1.1 is therefore essential.

The proof strategy. The circuit argument needs a function whose sign has small correlation with every moderately wide CNF. Write $g$ for its sign, equal to $+1$ on accepted inputs and $-1$ on rejected inputs. Correlation with a CNF indicator $H$ means $|\mathbb{E}gH|$ under uniform inputs. If a middle CNF feeds an exact OR representation of the function, it accepts only positive inputs, so $gH = H$. Small correlation then forces that middle gate to accept few inputs. Summing over the middle gates will contradict the function’s positive acceptance density.

Our main ingredient transfers this correlation problem to CNFs of constant width. Leave each variable live independently with probability $p$, and assign all other variables uniformly. Lemma 3.1 expresses each restricted width-$k$ CNF as a finite signed combination of width-$b$ CNFs. When $p \le1/2$ and $pk$ is bounded, a constant $b$ makes the expected total absolute coefficient mass at most two, independently of the number of clauses. Classical switching estimates also avoid a clause-count parameter, but change the normal form [6], Section 3, Main Lemma; here the tests remain CNFs. The proof expands by successive simultaneous clause violations. Counting the resulting paths backwards cancels the number of eligible clauses against a reciprocal violation count. This is the source of the clause-count independence.

We construct a language with a data block and parameter blocks. Membership evaluates a polynomial at a linear hash of the data, in the quotient ring specified by another input block. Fixing the parameter bits selects a function of the data bits, which we call a slice. For every desired lower-bound constant, probabilistic choices of these bits supply a slice with small correlation against every CNF of a suitable fixed width on most random restrictions. The language’s evaluator simply uses the supplied bits; it never has to find a hard slice or test irreducibility. The input-index construction of Paturi, Saks, and Zane [12], Section 5 uses the same idea of fixing parameters to obtain a hard subfunction.

To prove the slice’s correlation property, we combine the sunflower sparsification method of Impagliazzo, Paturi, and Zane [8], Section 2 with the disjoint refinement of Dell, Husfeldt, Marx, Taslaman, and Wählén [2], Appendix A of the full version. Lemma 4.1 gives the needed form: for every fixed width and every $\eta> 0$, the partition has at most $2^{\eta m}$ CNF pieces on $m$ variables, each of the same bounded width and with only linearly many clauses. There are few enough such sparse tests that a moment bound controls them simultaneously. Universal linear hashing and polynomial interpolation provide the limited-independent signs needed for this bound; Section 5 gives the sources and elementary arguments. Sparse normal forms and random polynomial families also occur in [8], Section 1.2.

The two probability estimates combine without an independence assumption. On restrictions where every narrow test has small correlation, we multiply that bound by the signed representation’s coefficient mass and use its expectation. On the exceptional restrictions, the correlation is at most one. This transfers the slice’s bound to every width-$k$ CNF. The constant-true CNF is one such test, so the slice is also nearly balanced.

Finally, a circuit with $S$ total gates has at most $S$ middle CNFs, each with at most $S$ clauses, even when bottom gates are shared. Deleting clauses wider than $k$ incurs total error at most $S^2 2^{-k}$. Section 6 chooses $k$ at the square-root scale. The correlations of the truncated CNFs bound the acceptance probabilities of the original middle gates, up to the deletion error. Those probabilities are too small to cover the positive inputs of the hard slice. The constants in the analysis depend on $A$; the language and its polynomial-time machine do not.

Clauses, correlation, and restrictions

We record the clause and restriction conventions needed for both structural lemmas.

For a finite coordinate set $V$, the cube $\{0,1\}^{V}$ carries the uniform probability measure. Expectations without a specified measure use this measure. A Boolean predicate is identified with its $0/1$ indicator. Its associated sign is $+1$ on accepted inputs and $-1$ otherwise.

A clause is an OR of literals, and a CNF is an AND of clauses. Tautological and constant-true clauses can be removed. Each remaining nonconstant clause uses distinct variables and contains no constants. Its scope is the set of these variables, and its width is the size of its scope. It is violated on exactly one assignment to its scope. A constant-false clause has empty scope and width zero. The empty CNF is the constant-true function.

For an integer $b \ge1$, let $C_b(V)$ be the set of CNF indicators on $\{0,1\}^{V}$ with clause widths at most $b$. There is no bound on the number of clauses. For $G:\{0,1\}^{V}\to\mathbb{R}$, define

The maximum exists: there are finitely many distinct clause indicators, and repetitions do not change a CNF’s function. Both constant functions belong to $C_b(V)$.

A $p$-random restriction of $[d]=\{1,\ldots,d\}$, for $0<p<1$, is sampled in two stages. Include each coordinate independently in a live set $T$ with probability $p$; then choose an independent uniform assignment $\rho$ to $[d]\setminus T$. For $G:\{0,1\}^{d}\to\mathbb{R}$, write $G_{T,\rho}$ for the function remaining on $\{0,1\}^{T}$. Filling the live coordinates with uniform bits produces a uniform point of $\{0,1\}^{d}$. Consequently, for any real-valued functions $G,H$ on $\{0,1\}^{d}$,

We will also use a cylinder: prescribing a pattern on $U\subseteq T$ and leaving $T\setminus U$ arbitrary. Its indicator is a conjunction of unit clauses, and its measure on the live cube is $2^{-|U|}$.

A restriction bound independent of clause count

A random restriction need not reduce every clause of a large CNF to small width. The following lemma instead expresses the restricted formula as a signed combination of small-width tests. The total absolute coefficient mass has a bounded expectation, regardless of the number of clauses. The normalization by counts of violated clauses is what makes this possible. This is a different conclusion from the classical switching estimate, which also has no clause-count parameter but changes the formula’s normal form [6] Section 3, Main Lemma. Here the tests remain CNFs; the cost is their signed coefficient mass, controlled in expectation.

Lemma 3.1 (Restriction bound). Let $k \ge0$ and $b \ge1$ be integers, let $H$ be a CNF of width at most $k$ on $[d]$, and let $0 < p < 1$. Choose $T \subseteq[d]$ by retaining each coordinate independently with probability $p$, and choose a uniform assignment $\rho$ outside $T$. Suppose

There are numbers $W(H,T,\rho) \ge0$, depending only on the formula and the restriction, such that

and, simultaneously for every real-valued function $G$ on $\{0,1\}^{T}$,

An empty sum in (3) is zero.

Proof. Discard true and tautological clauses from $H$, and list the remaining clauses as $C_1,\ldots,C_N$, retaining their indices even if clauses repeat. Let $E_i \subseteq[d]$ be the scope of $C_i$. Thus $|E_i| \le k$ and violation of $C_i$ prescribes one pattern on $E_i$. A false clause has empty scope and is always violated. All sums and families below are finite; there is no restriction on the finite number $N$.

Building the finite expansion. Fix $T,\rho$, and write $v_i(z)$ for the violation indicator of $C_i$ under this restriction. Put $q = \sum_i v_i$. For $U \subseteq T$, define

Call an index easy at $U$ if it occurs in the first sum, and hard at $U$ otherwise. Once the coordinates in $U$ are prescribed, an easy clause has at most $b$ variables still free. The classifications depend only on scopes, not on the values of $z$. In particular,

is the width-at-most-$b$ CNF obtained by conjoining the initially easy clauses after substituting $\rho$.

We will correct $K$ to obtain $H_{T,\rho}$. They already agree where $K=0$ and where $q=0$. At a point with $K=1$ and $q>0$, however, $K-H_{T,\rho}=1$, and every violated clause is initially hard. Dividing this unit excess among the violated clauses gives

The next step replaces the common denominator $q$ by counts of easy clauses. This produces further corrections, indexed by paths of successive clause violations.

A path $P=(i_1,\ldots,i_j)$ starts with $U_0=\varnothing$ and satisfies

Write $\mathcal{P}_j(T)$ for the family of these indexed paths. Each step adds at least $b+1$ coordinates, so their lengths are bounded by $L=\lfloor|T|/(b+1)\rfloor$. The selected indices are distinct: once an index is selected, its whole live scope belongs to $U_{h}$, and it stays easy thereafter. If all selected clauses are violated, their first $h$ indices are counted in $c_{U_h}$, and hence

Throughout this expansion, a path fraction is defined to be zero when its numerator vanishes. The displayed bound makes every denominator positive on the numerator’s support.

Continue to work at a point with $K=1$ and $q>0$. For a nonempty path $P=(i_1,\ldots,i_j)$, distinguish its remaining correction

from the contribution obtained by replacing the remaining factor $q$ in its denominator with $a_{U_j}$:

Since $q=a_{U_j}+\sum_{i\ \mathrm{hard\ at}\ U_j}v_i$, this replacement gives

where $P i$ denotes extension by $i$. Indeed, on the support of the prefix numerator, the sum over extensions is $t_P(q-a_{U_j})/q$, leaving $t_Pa_{U_j}/q=r_P$. If the prefix numerator vanishes, all extension numerators vanish too, so the identity still holds.

Initially $\sum_{P\in\mathcal{P}_1(T)}r_P=1$. Substituting (9) repeatedly gives, for $0\le s\le L$,

At $s=L$ there are no further paths, so the residual sum is empty. Together with the cases $K=0$ and $q=0$, this proves the pointwise identity on the whole live cube

The construction is finite; no convergence argument is involved.

Each path is a positive weight times a finite convex mixture. A path is compatible with $\rho$ if all its selected clauses can be violated simultaneously. Such violations prescribe exactly one pattern $\sigma_P\in\{0,1\}^{U_j}$, with no conditions on $T\setminus U_j$. Indeed, each selected clause prescribes its unique violating pattern; compatibility says that the prescriptions agree on overlaps and with $\rho$. Write

for this cylinder. Then $\prod_h v_{i_h}=\mathbf{1}_{Z_P}$. An incompatible path has zero numerator everywhere and can be omitted.

For a compatible path and each $h$, the function $c_{U_h}$ is constant on $Z_P$. Every clause in its defining sum uses only coordinates already fixed by $\rho$ and the pattern on $U_h$. Denote this positive integer constant by $c_h$, and set

On $Z_P$ we have $a_{U_h}=c_h+w_h$, where

Substitute both $\rho$ and the final pattern $\sigma_P$ into each clause indexed by $I_h$. The resulting clauses on $T\setminus U_j$ have width at most $b$, since $U_h\subseteq U_j$. Keep their original indices in this family, including clauses that become true or false and any repetitions. Thus $w_h$ remains exactly the number of violated clauses in this indexed family, even when some violations become constant after the final substitution.

We use the following elementary finite mixture. Given an indexed family of $a$ clauses and an integer $c\ge1$, uniformly permute the $a$ clause objects and $c$ distinct marker objects. Take the conjunction of the clauses appearing before the first marker. This finite uniform experiment defines a convex mixture of conjunctions of the indexed clauses. If an assignment violates exactly $w$ of the indexed clauses, the sampled conjunction holds precisely when the first object among those $w$ clauses and the $c$ markers is a marker. By symmetry its expectation is

The argument includes $a=0$, $w=0$, repeated clauses, and constant clauses.

Independently apply this mixture at each $h$ to the reduced clauses indexed by $I_h$, with $c=c_h$. Form $J_P$ by conjoining all sampled clauses, $K$, and the unit clauses prescribing $\sigma_P$ on $U_j$. Every realization of $J_P$ lies in $C_b(T)$; here the assumption $b\ge1$ permits the unit clauses. On the cylinder the independent mixtures have expected product $\prod_h c_h/(c_h+w_h)$, while off the cylinder $J_P$ vanishes. Consequently, as functions on the entire live cube,

The expectation here is over a finite auxiliary probability space. It does not involve the test function $G$.

Define $W_0(H,T,\rho)=1$, and, for $j\ge1$, let

For each fixed restriction, combine (10) and (13), then take the correlation with $G$ and use the triangle inequality. Since $K$ and every realization of every $J_P$ have width at most $b$, this gives (5). Both $W$ and all the mixtures were chosen without reference to $G$, so the inequality holds simultaneously for every real-valued $G$.

Reweighting by a full assignment. It remains to bound $\mathbb{E}W_j$. Generate a uniform full assignment $y\in\{0,1\}^d$ independently of $T$, and set $\rho=y|_{[d]\setminus T}$. This gives exactly the required distribution of restrictions. Conditional on $T,\rho$, the live part of $y$ is uniform. For a compatible path $P$, it lies in $\mathcal{Z}_P$ with probability $2^{-|U_j|}$; on that event every selected clause is violated and every $c_{U_h}$ equals $c_h$. Thus, conditional on each $T,\rho$, multiplying by $2^{|U_j|}$ exactly undoes the probability of its cylinder. In particular,

The identity holds separately for every path before summing. It does not assume that compatibility or the denominator counts are independent of the restriction.

Counting paths backwards. Fix $y$. For $R\subseteq[d]$, let

For a path counted in (15), put

where $D_h$ is used only for $h\ge1$. These sets satisfy

In particular, all displayed denominator counts are positive. Figure 1 depicts how a forward step removes $D_h$ from the live remainder and a reverse step adds it back.

The pair consisting of $T$ and its indexed path is determined by the terminal set $R_j$ and the successive reverse choices $(i_j,D_j),\ldots,(i_1,D_1)$. Indeed, each choice reconstructs $R_{h-1}=R_h\cup D_h$, recovering $T=R_0$ and every selected index. It is therefore enough to count reverse sequences starting from an arbitrary set $R$, allowing a choice of any $i\in V_R$ and any $D\subseteq E_i$ with $|D|>b$, followed by the state $R\cup D$. Because $E_i\cap R=\varnothing$, this step always adds $D$ disjointly. All actual reversed paths are included, and allowing additional sequences can only increase a sum of nonnegative weights.

Write

The sets $D_1,\ldots,D_j$ partition $U_j$, and $T = R_j \mathbin{\dot\cup} U_j$. The contribution of a given pair $(T,P)$, including the probability of its live set, therefore factors as

This formula explains the useful direction of counting: at state $R$, the reciprocal count is exactly $1/|V_R|$, the normalization for averaging over the possible clause indices at that state. For completeness, define the total weight of $s$ reverse steps from $R$ recursively by $F_0(R)=1$ and

The total weight of the choices at a state with $V_R\ne\varnothing$ is

When $V_R$ is empty the total weight is zero. Induction in (19) now yields $F_s(R)\le\theta^s$ for every $R$ and every fixed $y$. Notice that (20) averages over the clause indices instead of multiplying by their number. Repeated clauses cause no difficulty: their multiplicities occur in both the sum and $|V_R|$.

Use the injective reverse encoding and (18) to bound the expectation over $T$ inside (15), for this fixed $y$, by

Averaging over $y$ gives $\mathbb{E}W_j\le\theta^j$. Finally, all terms are nonnegative and $\theta<1$, so

as required. Empty formulas, false clauses, and empty live sets are already covered by the construction; if $k\le b$, there are no nonempty paths and $W=1$.

A disjoint sparse partition of bounded-width CNFs

We next reduce arbitrary bounded-width CNF tests to tests with only linearly many clauses. The proof adapts the sparsification method of Impagliazzo, Paturi, and Zane [8], Section 2, including its occurrence bounds, insertion accounting, and entropy count of branches. A disjoint refinement is described by Dell, Husfeldt, Marx, Taslaman, and Wahlén [2], Appendix A of the full version. Here we prove a version with the bookkeeping needed for our partition. Disjointness lets us add the correlations of the pieces without inclusion–exclusion.

Lemma 4.1 (Sparse partition). For every integer $b \ge1$ and real $\eta> 0$, there is a positive integer $M = M(b,\eta)$ with the following property. Every CNF indicator $H$ of width at most $b$ on $m \ge1$ variables can be written pointwise as

where the $H_a$ are CNF indicators of width at most $b$, each represented by at most $Mm$ clauses, and their satisfying sets are pairwise disjoint. The empty sum is permitted when $H = 0$.

We use the classical sunflower bound of Erdős and Rado [3] to identify a branching step, and include its short proof. A sunflower is a collection of distinct sets whose pairwise intersections all equal a fixed set $C$, called its core. The sets obtained by removing $C$ are its petals; they are pairwise disjoint.

Lemma 4.2. Let $s \ge0$ and $r \ge2$ be integers. A family of more than $s!(r-1)^s$ distinct sets of cardinality $s$ contains a sunflower with $r$ members.

Proof. For $s = 0$ there is at most one distinct set, so the hypothesis is impossible. Proceed by induction on $s$. If the family contains $r$ pairwise disjoint sets, these already form a sunflower with empty core. Otherwise, take a maximal pairwise disjoint subfamily. It has at most $r - 1$ members, and its union $U$ has at most $s(r - 1)$ elements. Maximality implies that every set in the original family meets $U$. Some element of $U$ therefore belongs to more than

members. Delete this element from all those members. The resulting sets remain distinct and have cardinality $s - 1$. By induction, $r$ of them form a sunflower. Restoring the deleted element gives the required sunflower in the original family.

Proof of Lemma 4.1. We regard clauses as sets of literals. Discard true and tautological clauses, duplicates, and any clause that contains another clause. If an empty clause remains, use the empty partition and stop. Otherwise the remaining clauses are nonempty and form an antichain under inclusion. The empty family is allowed and represents the constant true function.

The partition will come from a binary branching tree. Fix for now arbitrary integers $r_2,\ldots,r_b \ge2$; we will choose their values after bounding the number of leaves. A sunflower is eligible at size $i$ if it consists of $r_i$ size-$i$ clauses and has nonempty core. All set operations below concern literals. In particular, disjoint petals may contain opposite literals of one variable, and a branch may be unsatisfiable.

Branching and disjointness. Each state consists of an active antichain and a separate conjunction of unit clauses, called its side condition. Initially the side condition is true. It is never used to select sunflowers or to delete active clauses. Whenever an eligible sunflower exists, choose one of the smallest possible size $i$, with fixed deterministic tie-breaking, and write its clauses as

The core $C$ is nonempty. The petals are nonempty, pairwise disjoint, and all of the same size; their nonemptiness follows from distinctness and equal size of the sunflower members. Make two updates:

• On branch 0, insert the clause $C$ into the active family.

• On branch 1, insert all petal clauses $P_1,\ldots,P_{r_i}$ and append to the side condition the requirement that every literal of $C$ be false.

After either insertion, delete all subsumed active clauses to restore the antichain. Every inserted clause has size strictly less than $i$, so width never increases; the side condition uses only unit clauses. The extra requirement on branch 1 is the disjointness device of [2], Appendix A of the full version. Keeping it separate ensures that every deletion from the active family is caused by an active insertion, a fact needed in the counting argument below.

Every clause in an insertion batch is new and remains active immediately after the update. Indeed, an inserted clause $D$ is a strict subset of some current clause $A$. A current clause $B \subseteq D$ would satisfy $B \subsetneq A$, contrary to the antichain property. Within a petal batch, distinct equal-size clauses do not subsume one another either.

Let $F$ be the active CNF indicator before a step, and let $F_0,F_1$ be the active indicators after its two updates, without side conditions. Subsumption deletion preserves the conjunction, so

When $C$ is false, the selected clauses in $F$ require every petal to be true. Therefore

with disjoint supports on the right. Multiplying by the accumulated side condition gives the corresponding disjoint identity for the state. Once we prove termination, iteration of this identity will give a partition into leaf indicators.

Occurrence bounds and insertion budgets. We next bound the number of steps on every finite path prefix. The smallest-size rule bounds how many active clauses inserted in earlier branching steps can contain any one literal. Define

If the current size-$i$ clauses contain no eligible sunflower, each literal occurs in at most $e_i$ of them. For $i \ge2$, remove a fixed literal from the clauses containing it. More than $e_i$ distinct resulting sets would contain an $r_i$-member sunflower by Lemma 4.2; restoring the literal gives an eligible sunflower with nonempty core. For $i=1$, the claim follows because the clauses are distinct.

Call an active clause added if it was inserted in a branching step. At every state, for every size $u$ and every literal, we claim

Initially there are no added clauses. A step can increase this count only by inserting size-$u$ clauses, and such a step processes a size $i>u$. The smallest-size rule then guarantees that there is no eligible size-$u$ sunflower before the insertion. Thus the occurrence bound applies to all current size-$u$ clauses, giving at most $e_u$ occurrences of each literal. The insertion adds at most one further occurrence, because it adds either one core or pairwise disjoint petals. Deletions only decrease the count. This proves the invariant; the initial family itself need not satisfy an occurrence bound.

For any finite path prefix, let $N_u$ count the size-$u$ insertions, counting members of a batch individually. Every deleted added size-$u$ clause was subsumed by a newly inserted strictly smaller clause. Equality is excluded by the freshness of insertions, and side conditions never delete active clauses. Charge each such deletion to one smaller inserted clause that caused it. A fixed inserted clause $D$ receives at most $e_u+1$ charges: choose a literal of the nonempty clause $D$, and apply (22) just before its batch was inserted. Every size-$u$ clause subsumed by $D$ contains that literal. If several batch members could receive a charge, choose only one of them.

At the end of the prefix, at most $2m(e_u+1)$ added size-$u$ clauses are still active, since each is nonempty and there are only $2m$ literals. Counting deleted and surviving insertions therefore gives

Define the positive integers

The same recurrence holds for $i=1$ with an empty sum. Induction on $u$ in (23) proves

These bounds hold on every finite prefix, without assuming termination. Every step inserts at least one clause of size less than $b$, so every path has at most $m\sum_{u<b}D_u$ steps. The binary tree is therefore finite.

For $2\le i\le b$, put $F_i=\sum_{u<i}D_u$. Each step processing size $i$ contributes at least one insertion below size $i$, and each branch-1 step contributes exactly $r_i$ such insertions. Hence

Insertions caused by other processed sizes may also use this budget; including them only enlarges the upper bound.

Counting leaves and choosing thresholds. For each leaf and each $i=2,\ldots,b$, record in order the decisions made at steps processing size $i$, and pad this binary string with zeros to length $F_im$. By (26), it has at most $F_im/r_i$ ones. The tuple of strings determines the leaf. Indeed, distinct leaf paths have a first differing branch: neither can be a proper prefix of the other. Before this difference their states agree, so their selected size and their positions in that size’s stream agree. The different bits occur before padding in both streams, so the padded tuples remain different.

Write $h_2(x)=-x\log_2 x-(1-x)\log_2(1-x)$ for $0<x<1$. For integer $N$ and $0<x\le1/2$, the number of binary strings of length $N$ with at most $Nx$ ones is at most $2^{Nh_2(x)}$. A string with $j\le Nx$ ones has Bernoulli-$x$ probability

because $x/(1-x)\le1$. Their total probability is at most one, proving the bound even when $Nx$ is not an integer. Applied to the decision streams, this gives

We can now choose the thresholds to make this exponent small. The constant $F_i$ depends only on $r_2,\ldots,r_{i-1}$, because it involves only $D_u$ with $u<i$. Choose $r_2,r_3,\ldots,r_b$ in order, each large enough that

This is possible since $h_2(1/r) \to0$. An explicit choice is $r_i = 2^{q_i}$, where $q_i \ge1$ is the least integer satisfying $F_i(q_i+2)2^{-q_i} \le\eta/b$: the inequality $-(1-x)\ln(1-x) \le x$ implies $h_2(2^{-q}) \le(q+\log_2 e)2^{-q} < (q+2)2^{-q}$. For these choices,

Clause counts at the leaves. At a terminal state no eligible sunflower remains. The occurrence bound now applies to the entire active antichain: each literal occurs in at most $e_i$ size-$i$ clauses, so there are at most $2me_i$ such clauses. The side condition contributes at most $2m$ distinct unit clauses after repetitions are removed. Thus the leaf indicator has width at most $b$ and at most $Mm$ clauses, where

All constants depend only on $b$, $\eta$. An inconsistent side condition gives an empty piece, which may be discarded. The branching identities (21) give coverage and disjointness, and (28) bounds the number of pieces.

When $b=1$ there are no branching sizes or streams. The tree has one leaf, its empty product of stream counts is one, and at most $2m$ distinct unit clauses suffice; (29) gives $M=4$. The constant true function has the empty conjunction representation, and the constant false function can use the empty partition. This covers every $m \ge1$.

One explicit language and its hard slices

The language will evaluate a polynomial at a linear hash of its data bits. The hash and the polynomial coefficients are themselves input bits. This lets us choose them probabilistically when proving a lower bound, while keeping the membership algorithm fixed. We first define that algorithm on every input, then prove that suitable settings of its non-data bits give small correlation with every bounded-width CNF on most random restrictions. The input-index construction in [12], Section 5 supplies an earlier instance of this evaluator-and-hard-subfunction method. Its lower-bound model has bottom fan-in two; the correlation property proved below is the one needed for arbitrary fixed CNF width.

Definition 5.1 (The language). For an input of length $n$, put $d = \lfloor n/5 \rfloor$ and reject if $d < 64$. Otherwise define

Reject if fewer than $2d+(t+2)r-1$ input bits are available. Otherwise parse the input into the following consecutive blocks:

1. $d$ data bits $x=(x_1,\ldots,x_d)$;

2. $d+r-1$ hash bits $u_1,\ldots,u_{d+r-1}$;

3. $r$ bits $p_0,\ldots,p_{r-1}$, encoding the monic polynomial

4. $t$ blocks of $r$ bits, encoding elements $\beta_0,\ldots,\beta_{t-1}$ of the quotient ring $R_P = \mathbb{F}_2[Z]/(P)$, in the basis represented by $1,Z,\ldots,Z^{r-1}$.

Unused bits are ignored. Form

Let $\lambda:R_P\to\mathbb{F}_2$ take the degree-zero coefficient of the unique representative of degree less than $r$. The input belongs to $L$ exactly when

The matrix in (30) is Hankel (constant on anti-diagonals), or Toeplitz after reversing the data coordinates. Fully random Toeplitz matrices give a standard universal linear hash family [9], pp. 136–137. We use only the uniform image of each nonzero difference, proved below, not strong pairwise independence of hash values. Once the hash is injective on a restricted cube, polynomial interpolation supplies limited-independent values, as in [1], Section 6, proof of Proposition 6.3.

The rejection rule fixes the language at the small lengths once and for all. For $d\geq64$, the blocks always fit: they use

bits, and $r\leq2d^{2/3}$ and $t+2\leq2d^{1/6}$ imply $(t+2)r\leq4d^{5/6}\leq2d$. Thus (32) is at most $4d-1\leq n$. We also have $t\geq2$ and

Proposition 5.2. The language $L$ is decided on every input of length $n$ by one deterministic Turing machine in time $C(n+1)^a$, for some fixed positive integers $C,a$.

Proof. After the small-length check, the integer parameters can be computed without real arithmetic: $r$ is the least positive integer with $r^3\geq d^2$, and $t$ can be found by testing even integers until their sixth powers exceed $d$. Searching integers up to $n$ and using ordinary integer arithmetic takes polynomial time. Reading and checking the block boundaries does also.

Since $P$ is monic, division by $P$ gives a unique remainder of degree less than $r$, whether or not $P$ is irreducible. Thus every allowed polynomial block gives well-defined ring operations. Direct multiplication of two coefficient arrays and reduction by $P$ use $O(r^2)$ bit operations: form a polynomial of degree at most $2r-2$, then successively cancel its highest coefficients by shifted copies of $P$. Addition uses $O(r)$ bit operations. Formula (30) uses $O(rd)$ bit operations, and Horner evaluation of (31) uses $O(t)$ ring multiplications and additions. The evaluation therefore uses $O(rd+tr^2)$ bit-array operations and polynomial storage.

These are fixed loops on finite bit arrays, with counters of polynomial size. They can be implemented by a fixed Turing machine using direct tape scans, which incur only polynomial overhead per array operation. Together with the initial integer computations this yields a polynomial time bound; increasing its coefficient and exponent to positive integers gives the stated $C,a$ and covers the finitely many small lengths as well. In particular, the machine does not test irreducibility or search for any choice of parameter bits. Neither its instructions nor its running-time constants depend on the proof parameters used below.

For $d \ge64$ and fixed non-data bits, write $g : \{0,1\}^{d} \to\{-1,1\}$ for the sign of the resulting data function, with $+1$ on accepted inputs. It equals $(-1)^{\lambda(\sum_j \beta_j h(x)^j)}$. Although the evaluator allows every monic modulus, we will select an irreducible polynomial of degree $r$ for the hardness analysis. Such a polynomial exists for every $r \ge1$; an elementary proof is given in Lemma A.1 in Appendix A. The next proposition is the property of these slices that the circuit argument will use.

Proposition 5.3. For each fixed integer $b \ge1$ and real $B > 0$, all sufficiently large lengths $n$ admit fixed settings of the non-data bits such that, with

the resulting sign $g$ satisfies

Here $T$ includes each of the $d$ data coordinates independently with probability $p$, and $\rho$ is an independent uniform assignment outside $T$. In particular, the correlation bound on a good restriction holds simultaneously for all members of $\mathcal{C}_b(T)$.

Proof. Fix $b$, $B$ and take $d$ large enough that $0 < p < 1$ and $t \ge2$. Choose a monic irreducible polynomial $P$ of degree $r$, and identify $R_P$ with its field $F$ of size $2^r$. Initially choose all the hash bits $u$ independently and uniformly, and choose $\beta_0,\ldots,\beta_{t-1}$ independently and uniformly in $F$. We estimate the failure probability jointly over these choices and the restriction; the final step will fix one choice of these input bits.

Injectivity on a restricted cube. For any nonzero $w \in\{0,1\}^{d}$, the vector $h(w)$ is uniform in $\mathbb{F}_2^r$ over the hash bits. Indeed, let $s$ be the largest coordinate with $w_s = 1$. The $i$th row in (30) contains $u_{i+s-1}$ with coefficient one, and every other bit it uses has a smaller index. In particular no earlier row uses $u_{i+s-1}$. The $r$ rows therefore have independent successive pivots, so the linear map $u \mapsto h(w)$ has rank $r$ and takes a uniform input to a uniform output. Equivalently, after choosing the other bits, these pivot bits can be set successively in exactly one way to give any prescribed output. Thus $\Pr_u[h(w)=0] = 2^{-r}$.

Fix a restriction with $m = |T|$. Its affine data cube has exactly $2^m - 1$ nonzero differences, namely the nonzero vectors supported on $T$. Since $h$ is linear, two cube points collide exactly when their nonzero difference hashes to zero. A union bound gives

The fixed assignment $\rho$ only translates the hash image and has no effect on this estimate.

Limited independence from interpolation. Condition on a hash that is injective on this cube. At any $q \le t$ distinct cube points, let $a_1,\ldots,a_q \in F$ be their distinct hashes. For arbitrary desired values $v_1,\ldots,v_q \in F$, the polynomial

has degree at most $q-1 < t$ and satisfies $Q(a_i)=v_i$. The denominators are nonzero field elements. Consequently the linear map from $(\beta_0,\ldots,\beta_{t-1}) \in F^t$ to the $q$ evaluation values is surjective. Each fiber is a translate of its kernel and hence has the same size, so uniform coefficients give independent uniform values in $\mathbb{F}^q$. The coordinate map $\lambda$ is a nonzero $\mathbb{F}_2$-linear map, with $\lambda(1)=1$. Its two fibers have equal size, for translation by $1$ interchanges them. Applying $(-1)^\lambda$ coordinatewise therefore gives unbiased, $t$-wise independent signs on the restricted cube.

One bound for every sparse test. Apply Lemma 4.1 with $\eta=1/8$ and write $M=M(b,1/8)$ for its positive integer constant. On a cube of dimension $m\ge1$, the number of possible normalized clauses of width at most $b$, including the false clause of width zero, is

For the inequality, list a clause’s literals in a fixed order and pad to length $b$ with a symbol outside the $2m$ literals; this is an injective encoding. A CNF with at most $Mm$ clauses can in turn be encoded by a list of length $Mm$ over these $C_m$ clauses and a padding symbol. In particular the number of such CNF indicators is at most

This list includes the constant true test (no clauses) and the constant false test (one empty clause).

Fix one such test $J$, and write $Y=\sum_{z\in\{0,1\}^T}g_{T,\rho}(z)J(z)$. Expectation in the next calculation is over the coefficients $\beta_j$, conditional on the injective hash. Expand $Y^t$ as a sum over ordered $t$-tuples of cube points. If some point occurs exactly once, its sign is independent of all the other distinct signs in the term and has mean zero, so that term’s expectation vanishes. Otherwise at most $t/2$ distinct points occur. All such tuples are covered by listing $t/2$ cube points, with repetitions allowed to pad the list, and choosing a position in that list for each of the $t$ factors. There are at most $2^{mt/2}(t/2)^t$ such descriptions. Each term has absolute expectation at most one, and hence

Because $t$ is even, $Y^t=|Y|^t$. Markov’s inequality, obtained by bounding $|Y|^t$ below by a threshold on its exceedance event, gives

By (36), the probability that any sparse test has $|\mathbb{E}_zg_{T,\rho}(z)J(z)|>2^{-m/4}$ is at most

whenever

This condition holds uniformly for $m_0/2\le m\le2m_0$ once $d$ is sufficiently large. Indeed, with $b,B,M$ fixed, (33) bounds the two summands respectively by $O_{b,B,M}(\log d/d^{1/6})$ and $O_B(\log d/\sqrt d)$, both tending to zero.

If no sparse test fails, any $J\in\mathcal{C}_b(T)$ is, by Lemma 4.1, a sum of at most $2^{m/8}$ indicators from the sparse list. The triangle inequality thus gives

The sparse event already controls every indicator in the list, so this conclusion holds for every width-$b$ CNF simultaneously. No further probability estimate depends on the choice of $J$.

Restriction tails and a fixed setting. The variable $m = \lvert T\rvert$ is binomial with mean $m_0$. Independence and $1+v \le e^v$ give

Markov’s inequality in these two estimates yields

Both displayed exponents have coefficient greater than $1/16$. For example, tangent and secant bounds for $1/x$ on $[1,2]$ give $2/3 < \ln2 < 3/4$, and therefore $4/3 < \log_2 e < 3/2$. The total probability of leaving the prescribed range is at most $2 \cdot2^{-m_0/16}$.

For every restriction in that range, (35) and (39) bound the conditional failure probability over the parameter bits by $2^{m-r}+2^{-mt/8}$. Uniformly in this range,

for all sufficiently large $d$: the first inequality follows from $r/m_0 \to\infty$, by taking $r \ge(2+1/16)m_0$, and the second from $m \ge m_0/2$ and $t \ge1$. Adding these two errors and the two restriction tails gives joint failure probability at most $4 \cdot2^{-m_0/16}$.

For each fixed choice of $(u,\beta_0,\ldots,\beta_{t-1})$, let its failure probability be the probability over $(T,\rho)$ of the event in (34). The average of these finitely many numbers is the joint failure probability just bounded. At least one setting therefore has failure probability at most $4 \cdot2^{-m_0/16}$. Fix that setting, the already selected $P$, and arbitrary unused bits. This proves the proposition.

The choices in Proposition 5.3 may depend on $b$, $B$ and the input length. The quantifiers require only that $b$, $B$ be fixed before the length tends to infinity. These choices select restrictions of the single language in Definition 5.1; computing membership never requires finding them.

The depth-three circuit lower bound

We now combine the two structural lemmas with the hard slices. The order of choices is useful: fix the proposed circuit exponent $A$, then choose constants $B$, $b$, and only then let the input length grow. All choices of parameter bits remain restrictions of the language already defined.

Proof of Theorem 1.1. Proposition 5.2 supplies the single polynomial-time machine. Fix $A > 0$, and put

All subsequent assertions hold for every sufficiently large $n$, with the threshold allowed to depend on $A$. In particular, $0 < p \le1/2$ and $n \le9d$, so

Choose a constant target width. Since $k \le[3(s+1)+1]\sqrt{d}$ for $d \ge1$, we have

Choose an integer $b \ge1$, depending only on $A$, so large that

Such a choice exists: once $\ell+1 \ge2Q$, successive terms have ratio at most $1/2$, and the tails tend to zero. Using $\binom{k}{\ell}\le k^\ell/\ell!$, the parameter of Lemma 3.1 satisfies

This is the only place where the desired circuit exponent affects the target width.

Transfer correlation to width $k$. Fix a setting of the non-data bits supplied by Proposition 5.3, and let $g:\{0,1\}^{d}\to\{-1,1\}$ be the sign of that slice. Call a restriction good if it lies outside the failure event in (34). On such a restriction,

The exceptional probability is at most $4\cdot2^{-m_0/16}$.

For any fixed $H\in C_k([d])$, Lemma 3.1 gives a nonnegative $W_H$ with $\mathbb{E}W_H\le2$ and $|\mathbb{E}_zg_{T,\rho}H_{T,\rho}|\le W_H\operatorname{corr}_{b}(g_{T,\rho})$. On an exceptional restriction the same absolute correlation is at most one, since $g$ is a sign and $H$ is an indicator. Equation (2) therefore yields

The good event and $W_H$ need not be independent. Moreover, the setting of the non-data bits was fixed before $H$ was chosen: the good event controls all width-$b$ tests simultaneously, and the restriction lemma applies to each width-$k$ test. Thus (47) holds for every such $H$ for this one slice.

The constant true test is a width-$k$ CNF. Applying (47) to it gives $|\mathbb{E}g|\le6\cdot2^{-m_0/16}$. The accepted set of the slice consequently has density

for every sufficiently large $n$.

Remove wide bottom clauses and count every gate. Suppose, for a contradiction, that the $n$-bit membership function has an OR–AND–OR circuit with $S\le2^{A\sqrt{n}}$ total gates. Delete every gate with no directed path to the output, so every remaining middle gate feeds the top OR. Fix its non-data inputs to the setting just chosen. This does not increase its number of gates. There are at most $S$ middle AND gates. Each is the indicator of a CNF $H$ whose clauses are the outputs of its distinct bottom OR gates, and hence it has at most $S$ clauses. A bottom gate shared between several middle gates still supplies at most one clause to each; repeated wires can be removed.

Normalize the clauses after the inputs are fixed. A middle gate with a false clause computes zero and can be omitted. For any remaining middle CNF $H$, delete every clause of width greater than $k$, and denote the resulting width-$k$ CNF by $H'$. Then $H' \ge H$. A normalized clause of width $\ell> k$ is false on a fraction $2^{-\ell} \le2^{-k}$ of the cube, so a union bound over its at most $S$ deleted clauses gives

Every input accepted by $H$ is accepted by the top OR, which computes the slice exactly. Hence $gH = H$ pointwise, and

Here $\lvert g\rvert= 1$ bounds the truncation error, and (47) bounds the first term.

The accepted set is the union of the sets accepted by the middle gates. Summing (50) over at most $S$ of them, and using (44), gives

Indeed, $m_0/16 = 4(s+1)\sqrt{d}$ and $k \ge3(s+1)\sqrt{d}$. This contradicts (48). For the fixed $A$, every sufficiently large $n$ therefore satisfies $S_3(f_n) > 2^{A\sqrt{n}}$. Since $A > 0$ was arbitrary and the language and its machine are fixed, Theorem 1.1 follows.

Irreducible polynomials over $\mathbb{F}_2$

Lemma A.1. For every integer $r \ge1$, there is a monic irreducible polynomial of degree $r$ over $\mathbb{F}_2$.

Proof. First construct an extension field in which $X^{2^r} - X$ splits. Any nonconstant polynomial over a field has an irreducible factor, by choosing a nonconstant divisor of least degree. The quotient by an irreducible polynomial is a field: the Euclidean algorithm expresses $1$ as a linear combination of that polynomial and any nonzero residue representative, giving the inverse of the latter. Adjoining a root by this quotient and factoring out the corresponding linear factor can be repeated. Each step reduces the degree still to be split, so finitely many such extensions suffice.

In the resulting field the roots of $X^{2^r} - X$ are distinct, since its formal derivative is $-1 = 1$. There are exactly $2^r$ roots. Their set $F$ contains $0,1$ and is closed under addition and multiplication: in characteristic two, repeated squaring gives $(a+b)^{2^r}=a^{2^r}+b^{2^r}$, and the analogous product identity is immediate. For a nonzero root $a$, the identity $(a^{-1})^{2^r}=(a^{2^r})^{-1}=a^{-1}$ gives closure under inversion. Negatives equal the original elements in characteristic two. Thus $F$ is a field with $2^r$ elements. A basis of $F$ over $\mathbb{F}_2$ has exactly $r$ elements, because a vector space of dimension $v$ over $\mathbb{F}_2$ has $2^v$ elements.

For $a \in F$, let its monic polynomial of smallest positive degree over $\mathbb{F}_2$ that vanishes at $a$ have degree $e$. Such a polynomial exists by linear dependence in $F$, and it is irreducible: a proper factorization would give a smaller vanishing factor in the field $F$. Polynomial division shows that evaluation identifies $\mathbb{F}_2[a]$ with its quotient field, with basis $1,a,\ldots,a^{e-1}$. It therefore has $2^e$ elements. Regarding $F$ as a vector space over this subfield shows $e \mid r$: if its dimension is $v$, the products of the two bases give an $\mathbb{F}_2$-basis of size $ev=r$.

Every element of a field with $2^e$ elements satisfies $a^{2^e}=a$. For nonzero $a$, multiplication by $a$ permutes the nonzero elements; taking their product and cancelling gives $a^{2^e-1}=1$. Zero satisfies the identity as well. Hence each element of $F$ of degree $e$ is among the at most $2^e$ roots of $X^{2^e}-X$. Here the usual root bound follows by repeatedly dividing by $X-a$ for distinct roots. If $e<r$ and $e\mid r$, then $e\le\lfloor r/2\rfloor$. The number of elements of degree less than $r$ is consequently at most

with the sum empty for $r=1$. Some element of $F$ has degree $r$, and its monic minimal polynomial is the required irreducible polynomial.