Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

Introduction

Circuit complexity is one of the most fundamental and well studied areas in theoretical computer science. Once viewed as a promising approach towards proving NP $\ne$ P, the ultimate goal is to find some function in the class NP which requires super-polynomial circuit size. Unfortunately, the results remain far from satisfactory. For general fan-in-two Boolean circuits over the full binary basis, Li and Yang [17] proved an explicit size lower bound of $3.1n-o(n)$, and a recent preprint of Mishra and Santhanam [18] reports an improvement to $3.5n-o(n)$, despite the fact that a random Boolean function requires exponential circuit size with high probability. On the other hand, we do have exponential lower bounds for restricted circuit classes, and one of the most extensively studied cases is the class of AC$^0$, which captures constant depth circuits with AND and OR gates of unbounded fan-in.

Here, the celebrated result of Håstad [9] (see also [1, 5, 26, 20, 21]) shows that the parity and majority functions both require $2^{\Omega(n^{1/(d-1)})}$ size depth-$d$ AC$^0$ circuits. Subsequent work has refined these bounds and developed alternative proofs [11, 8, 15, 14]. For parity, this is well known to be optimal, i.e., there exists a size $2^{O(n^{1/(d-1)})}$ depth-$d$ AC$^0$ circuit that computes parity. For majority, this was not known until the recent result of Lecomte and Ramakrishnan [16], which constructed depth-$d$ AC$^0$ circuits of size $2^{O(n^{1/(d-1)})}$ for every symmetric function. Hence, the bound is also optimal for majority, and in particular, no symmetric function can break this bound.

Breaking this barrier, and proving stronger lower bounds for AC$^0$ circuits has since been one of the central open problems in circuit complexity. This question is important both in its own right and because of its connections to general circuit lower bounds. For example, Valiant [23, 24] showed that any function computed by a linear size Boolean circuit of fan-in two and logarithmic depth can also be computed by a depth-three AC$^0$ circuit of size $2^{O(n/\log\log n)}$, so an explicit function with a depth-three AC$^0$ lower bound of $2^{\omega(n/\log\log n)}$ would also give the first superlinear size lower bound for logarithmic depth general Boolean circuits. We refer the reader to [25, 7] for further discussions of the connections between AC$^0$ lower bounds and general circuit lower bounds.

Four decades after Håstad’s result, a recent paper by OpenAI [19] breaks the depth three barrier, and gives an explicit function that requires OR–AND–OR circuits of size $2^{\omega(\sqrt{n})}$. As observed by Chukhin [3], their proof implicitly gives the quantitative bound of $2^{\Omega(\sqrt{n\log\log n/\log\log\log n})}$. Subsequently, Chukhin [3] improved the result and obtained a lower bound of

at every fixed depth $d \ge3$ for a particularly simple trilinear function.

In this paper, we further improve Chukhin’s result and obtain stronger lower bounds.

Results

Without loss of generality, we consider unbounded-fan-in AND/OR circuits with negations only at the inputs. This at most doubles the size of the AC$^0$ circuit. Size counts all AND and OR gates, including bottom-layer gates; input negations are free. Depth is the largest number of gates on an input-to-output path. Arbitrary fan-out is allowed, so subcircuits may be shared. We obtain both worst case and average case hardness results. For average case hardness, we define the correlation of two Boolean functions $F,C$ on $n$ bits to be

Thus the absolute deviation of the agreement probability from $1/2$ is $\operatorname{Corr}(F,C)/2$. All logarithms are base two unless written $\ln$.

Worst-case hardness. For a fixed binary basis of $E = \mathbb{F}_{2^N}$, let

Thus $I_N$ is the trace component of the inverse map, with inversion extended by $\operatorname{inv}_0(0) = 0$. At $N = 2^j$ we use an explicit quadratic tower; at other lengths we pad from the largest such $N$. Denote the resulting family by $F_n$. This family is fixed independently of the circuit depth and size.

The coefficient input $z$ in the trilinear function is part of the input. Likewise the evaluator’s hash, modulus, and polynomial coefficients are counted. Hard parameter settings can be selected nonconstructively in a lower-bound proof without changing the uniform algorithm computing the full function. At depth three the lower bound is $2^{\Omega(\sqrt{n \log n})}$.

Average-case hardness. The inverse-trace family has an additional property that permits control of arbitrary circuit correlation, uniformly from polynomial size to a subexponential size range.

This improves the classical correlation benchmark of parity in [10] by a factor of $\log\log S$ in the exponent. For $S = n^B$, with $B > 1$ fixed, the exponent in Eqn. (2) is $\Omega_{d,B}(n \log\log n/(\log n)^{d-1})$. For $S = 2^{n^\alpha}$ and fixed $0 < \alpha< 1/(d-1)$, it is $\Omega_{d,\alpha}(n^{1-\alpha(d-1)} \log n)$. For example, depth-three circuits of size $2^{n^{2/5}}$ have correlation at most $2^{-\Omega(n^{1/5}\log n)}$.

Tal’s Fourier-tail theorem [22], together with the uniform bound on the Fourier coefficients of inverse trace, also gives the comparison bound $2^{-\Omega_d(n/(\log S)^{d-1})}$ for inverse trace. Our bound gains a factor $\log\log S$ in this exponent; the comparison is proved in Section F. This comparison concerns the bound obtained from Tal’s theorem; we do not claim to subsume all previous correlation bounds. Also, the size range in Theorem 1.2 is smaller than the worst-case threshold in Theorem 1.1. The latter does not follow by substituting its threshold into Eqn. (2).

Explicit upper bounds for inverse trace. The same inverse-trace family also admits subexponential-size circuits at sufficiently large fixed depths. Write $\operatorname{sized}(G)$ for the minimum number of AND/OR gates in a depth-at-most-$d$ circuit computing $G$, with free input negations and arbitrary sharing. For a triple $\mathbf{h}=(h_1,h_2,h_3)$ of positive integers, put

Let $U_d(N)$ be the minimum of $N$ and these quantities over all such triples with $h_1+h_2+h_3+1\le d$; if $d=2,3$, set $U_d(N)=N$.

Together with Theorem 1.1, this places the exact circuit complexity of one fixed explicit family between

The upper bound is subexponential at every fixed depth $d\ge8$. There remains a gap with the lower bound; at depths three and four, this construction gives only the full-DNF exponential estimate. We do not claim that the upper bounds are optimal or that depth eight is the first depth admitting subexponential circuits.

The proof uses the evaluation and interpolation approach to finite-field arithmetic of Healy and Viola [12]. We implement three stages directly at constant depth: linear evaluation followed by logarithm tables, multiplication of the evaluated factors, and a final parity. Each stage can be viewed as a computation with few state bits, and enumerating intermediate states gives an adjustable depth–size tradeoff. Choosing the gate orientations at the two stage boundaries saves two layers. § 7 gives the construction and its depth accounting. All final gates are ordinary AND/OR gates, with negations only at the inputs.

Proof Overview

We prove our lower bounds by establishing the following main technical theorem.

We first note that $\operatorname{cl}_b(A)$ is the set of satisfying assignments of a width $b$ CNF. Indeed, for a subset $I \subseteq[m]$ define the projection $\pi_I : \pi_I(x) = x|_I$ and $\pi_I(A) = \{a|_I : a \in A\}$. Then for any $z \in\{0,1\}^I$ such that $z \notin\pi_I(A)$, any $x \in\operatorname{cl}_b(A)$ must satisfy that $\pi_I(x) \ne z$. Hence, let

then

It is also not hard to see that $\operatorname{cl}_b(A)$ is the smallest satisfying assignment set of any width-$b$ CNF that contains every string in $A$. In this sense, we can use a list $A$ to describe a CNF, without listing its clauses. This is particularly useful because the CNF can have a large number of clauses.

On a high level, our proof of lower bounds follows the same framework as in [3] and [19], by first reducing the problem to bounding correlations with width-$b$ CNFs for an appropriate choice of $b$. The key step in the analysis is to make sure that restrictions of the hard function have small correlation with all width-$b$ CNFs. However, the number of such CNFs is very large, hence [3] uses the CNF sparsification results developed by Impagliazzo, Paturi, and Zane [13], and refined by Calabro, Impagliazzo, and Paturi [2] to reduce the case to CNFs with few clauses. The number of such CNFs is much smaller than general width-$b$ CNFs, and therefore a union bound suffices. However, this approach still results in $b^{O_\varepsilon(b)}m$ clauses, which only permits $b = \Theta(\log n/\log\log n)$ as in [3].

Here, we instead use our point-list decomposition, so that the problem is reduced to bounding the correlation with all width-$b$ CNFs that are described by a short list. The counting of such lists pays a better price in the union bound, replacing the $b^{O_\varepsilon(b)}$ dependence from clause sparsification by $2^{O_\varepsilon(b)}$, thus allowing $b = \Theta(\log n)$ even when the pieces have many clauses. Consequently, our theorem does not resolve the algorithmic CNF sparsification problem asking for pieces with only $2^{O(b)}m$ clauses.

Why short point lists improve the exponent. Let $\kappa_b(g) = \max_H |\mathbb{E}[gH]|$, where $H$ ranges over all width-$b$ CNFs and $g$ is a sign function. The maximum includes the constant-one CNF. Here $H$ is a $\{0,1\}$-valued indicator: $\kappa_b$ measures correlation with CNF indicators, whereas $\operatorname{Corr}$ uses the $\{-1,1\}$ encodings of both Boolean functions. A decomposition into $2^{\varepsilon m}$ pieces gives

There are fewer than $2^{mL+1}$ lists of length at most $L$ when $m \ge1$. The simultaneous moment argument therefore pays $O(mL)$ description bits. With our theorem, $L = 2^{O_\varepsilon(b)}\log(m+1)$; hence widths $b$ proportional to $\log n$ remain affordable.

Here is the parameter calculation behind the worst-case result. Write $\ell= \log S$. Standard depth reduction leaves a depth-three circuit with bottom fan-in $k = \Theta_d(\ell)$ and survival probability $q = \Theta_d(\ell^{-(d-3)})$. A second restriction of survival $p = b/(64k)$ transfers width $k$ to width $b$ in expected signed coefficient mass. The expected number of free variables after both restrictions is

Moment bounds and point-list counting give expected maximum bounded-width CNF correlation $2^{-\Omega(m)}$. An exact circuit covers a constant fraction of the cube by at most $S^{O_d(1)}$ monochromatic CNFs, forcing $m = O_d(\ell)$. Taking $b = \Theta_d(\log n)$ and solving this relation gives $\ell= \Theta_d((n\log n)^{1/(d-1)})$.

The trilinear function and the evaluator in [19] provide moments through random parameter inputs. Inverse trace provides them through translations in a binary field, and Weil bounds for additive character sums. Its rational character sums remain controlled after conditioning on a coordinate subcube, paying explicitly for its codimension. This robustness is used in the average-case proof.

From exact computation to small correlation. For an exact circuit with OR output, the satisfying assignments of every CNF child lie in one level set of the target. Its density is therefore an absolute correlation. A circuit that makes errors has no such property: the accepting sets of its CNF children may overlap and contain inputs from both level sets of the target. Bounding each child alone does not bound the top OR’s correlation.

We instead switch the entire restricted circuit down to depth two. For a circuit with bottom fan-in $O(\ell)$, $d-2$ switching stages followed by CNF width reduction leave an expected number of free variables

using $b = \Theta(\log\ell)$. The switching lemma gives failure probability only $2^{-\Omega(\ell)}$, which is insufficient when $m \gg\ell$. Common partial decision trees allow a much smaller failure probability $2^{-\Omega_d(m)}$.

The cost of a common partial decision tree is paid through an exact expansion. At a leaf, let $P$ indicate its path and let $H$ be a residual CNF. Then $PH$ is still a CNF of the same width: the path contributes unit clauses, irrespective of the path length. A DNF leaf is written as $P-PH$. Thus a tree of depth $R$ gives signed coefficient mass at most $2^{R+1}$ in bounded-width CNFs. Choosing $R$ as a sufficiently small depth-dependent fraction of $m$ leaves an exponentially decaying correlation.

Finally, simply replacing bottom gates of large fan-in by their typical values introduces an error of order $S2^{-k}$, again too large when $m \gg\ell$. We remove it by a signed cofactor recursion. Each exceptional assignment fixes many coordinates and incurs its full probability. The bounded-width CNF estimate holds uniformly on large coordinate subcubes, so the recursion can continue until its residual probability is $2^{-\Omega(n)}$.

Organization and dependencies. § 2 to § 4 prove the point-list theorem and the inverse-trace restriction estimate. § 5 proves the correlation theorem, with detailed switching parameters and parameter checks in Sections A to B. § 6 gives the common worst-case reduction; Section D supplies the two other targets. § 7 gives the complementary nonuniform upper bounds for inverse trace. § 8 compares these bounds and discusses the limits of the lower-bound method. The external inputs are the switching lemma and multi-switching lemma of Håstad (the latter in Tal’s formulation), rational additive-character bounds, and the trilinear restriction moments of Chukhlin. Statements and locations are given where used. All other reductions are proved here.

An exact decomposition by lists of satisfying assignments

A clause is a disjunction of literals, and a CNF is a conjunction of clauses. Its width is the maximum number of variables in a clause. We remove tautological clauses and repeated literals. We identify a CNF with its Boolean indicator or its set of satisfying assignments, as appropriate. The constant-zero and constant-one functions are allowed, represented by an empty clause and an empty conjunction, respectively. The closure in Eqn. (7) forbids exactly the coordinate patterns of width at most $b$ absent from $A$.

Proof. Fix a deterministic order of partial assignments on at most $b$ coordinates. At a nonempty current set $S$, query the first pattern $\rho$ with

if one exists. Split $S$ into the true child $S\cap[\rho]$ and the false child $S\setminus[\rho]$. Both children are nonempty and smaller than $S$. The true child adds unit clauses; the false child adds the clause forbidding $\rho$. Every state remains a width-$b$ CNF on the original $m$ coordinates. The process terminates and its leaves partition $H$.

Every true branch decreases $\log|S|$ by more than $Cb$. Hence a nonempty terminal path has at most $m/(Cb)$ true branches. Let $\sigma$ be the union of their partial assignments. It is consistent, every terminal satisfying assignment extends it, and $|\operatorname{dom}\sigma|\le m/C$. Here $\operatorname{dom}\sigma$ means the domain of the partial assignment $\sigma$.

Distinct leaves have distinct $\sigma$. At their first divergence, one takes the true branch of a pattern $\rho$. Its fingerprint $\sigma$ extends $\rho$. If the other leaf had the same fingerprint, all its satisfying assignments would extend $\rho$, contrary to its false branch. Thus one partial assignment records enough information to distinguish the leaves; neither query order nor negative answers need be stored. The leaf count is at most

We used the binomial entropy estimate $\sum_{j\le r}\binom{m}{j}\le2^{mh_2(r/m)}$ for integer $0\le r\le m/2$ and monotonicity of $h_2$ on $[0,1/2]$.

At a terminal set $J$, every occurring pattern on at most $b$ coordinates has probability at least $\theta=2^{-Cb}$. There are at most $(2m+1)^b$ such patterns: encode the sorted literals and pad the remaining slots. With $L=L_C(m,b)$ independent uniform samples from $J$, the probability of missing any occurring pattern is at most

Therefore we can choose a covering list $A$ with $|A| \le L$. Every local pattern of a point of $J$ is in $A$, so $J \subseteq\operatorname{cl}_b(A)$. Conversely, a point outside $J$ violates one of its width-$b$ clauses. That falsifying pattern occurs in no satisfying assignment of $J$, hence in no row of $A$, and the point is outside $\operatorname{cl}_b(A)$. Thus $J = \operatorname{cl}_b(A)$ exactly.

Since $\varepsilon_C \to0$, the theorem implies Theorem 1.4. We will use

which follow from $h_2(u) \le u\log(e/u)$. Lists of lengths one through $L$ define fewer than $2^{mL+1}$ tests for $m \ge1$, regardless of their clause counts.

A small example. For $b = 1$, the closure retains exactly the coordinate values present in the rows. The list $A = \{000,110\}$ has closure $\{000,010,100,110\}$: the first two bits are unrestricted and the last is zero. For $b = 2$, the same list has closure $\{000,110\}$, since the first two bits must agree. The width parameter specifies which local patterns a list must preserve.

The decomposition also adapts to the number of satisfying assignments.

Proof. The logarithmic cardinality budget starts at $h$, so each fingerprint has at most $h/C$ fixed coordinates. Count as above. Disjointness and Cauchy–Schwarz give $\sum_i\sqrt{\mu_{J_i}} \le\sqrt{R\mu_H}$.

Restriction transfer without a clause-count loss

For a real function $G$ define

Equivalently, $\operatorname{Mass}_b(G)$ is the minimum $\ell_1$ norm of the coefficient vector over all exact expansions into width-$b$ CNFs. It is the quantity denoted $\operatorname{size}_b(G)$ by Chukhin [3 Section 2]. Then $|\mathbb{E}[gG]| \le\operatorname{Mass}_b(G)\kappa_b(g)$. Multiplication by a conjunction of unit clauses does not increase this mass. A $p$-random restriction independently keeps a variable free with probability $p$ and otherwise fixes it to a fair bit. Composition of independent $q$- and $p$-restrictions has the $qp$ product distribution.

Proof. We include the mass argument to make its independence of the clause count explicit. Order the clauses, and let $H_i$ be the conjunction of the first $i$. For the next clause $D$, call it wide if no literal is fixed true and more than $b$ variables remain free. Let $v_D$ be the conjunction falsifying the remaining literals, and let $\rho_D$ extend $\rho$ by these assignments. On a wide restriction,

The last cofactor is extended to the original cube of free variables by ignoring its additional fixed coordinates. The mass is at most the sum of the two previous masses. If $\rho$ falsifies $D$, the new mass is zero. In every other nonwide case, adding $D_\rho$ to each summand does not increase mass.

Each preimage of a restriction $\sigma$ falsifying $D$ is obtained by freeing $j>b$ of its at most $k$ clause variables. Its product probability is $(2p/(1-p))^j$ times that of $\sigma$. Summing the extra wide-case mass therefore costs at most $\vartheta$ times the previous mass on restrictions falsifying $D$, precisely the mass removed in that case. Expected mass cannot increase as clauses are added. It starts at one for $H_0=1$.

For $p=b/(64k)$, $2p/(1-p)\le4p$, and each summand with $j>b$ is at most $(eb/(16j))^j\le4^{-j}$. Their sum is below one.

Proof. Fix $\phi$ and a width-$k$ CNF $H$ before drawing $\rho$. Averaging a restriction and filling its free variables reproduces the uniform input distribution. Thus

On a bad restriction we use $|\mathbb{E}[g_{\phi\rho}H_\rho]|\le1$. The right side is independent of $H$, so we can maximize over $H$ and then average $\phi$.

The order matters: the resulting CNF may depend on all outer circuit restrictions. It is selected before the fresh inner restriction used in Theorem 3.2. We never assume independence between the good event and coefficient mass.

Inverse trace against every restricted CNF

Let $E=\mathbb{F}_{2^N}$ with a fixed binary basis, $\psi(x)=(-1)^{\operatorname{Tr}(x)}$, and $f(x)=\psi(c\operatorname{inv}_0(x))$ for $c\ne0$. Inverse trace corresponds to $c=1$. A coordinate subcube $V=x_0+W$ fixes some basis coordinates; its codimension $b_0$ is the number fixed. Expectations on subcubes are normalized.

If $u_i \in W$ and $V = x_0 + W$ has codimension $b_0$, then

Proof. Off its poles the summand in Eqn. (14) is $\psi(r(x))$ for

Its finite poles are simple with nonzero residues. It cannot be $R^2-R$ over the algebraic closure, since every pole of such a nonconstant expression has even order. Apply the rational additive-character estimate, for example Fu–Wan [4 Theorem 4.6, version 3], with extension degree one, trivial multiplicative character on $\prod_i(X+u_i)$, and additive argument $r$. In their notation $D_1=D_3=h$, $D_4=0$, and $D_2\le1$, giving an unnormalized bound at most $2h\,2^{N/2}$ off the poles. Restoring the at most $h$ values at the poles under our convention $\operatorname{inv}_0(0)=0$ proves Eqn. (14) with slack.

Let $W^\perp$ be the annihilator of $W$ under the nondegenerate trace pairing. Orthogonality gives

Normalized conditioning is therefore a sum of $2^{b_0}$ twisted full-field expectations. Apply Eqn. (14) to each.

Proof. Expand over $2t$ independent uniform points $z$. Tuples in which each point has even multiplicity are covered by the $(2t-1)!!$ pairings of positions. Each pairing has total $J$-weight $(\mu2^{-v})^t$. Every other tuple leaves a nonempty set of at most $2t$ distinct shifts of odd multiplicity. Apply Eqn. (15); all tuple weights are nonnegative and their total is $\mu^{2t}$.

The paired term behaves like a moment bound for limited independence. The second term is the character-sum error term. Our list count must fit within the exponential bound supplied by the latter.

Proof. Draw a fresh inner $p$-restriction $\rho$. The number $v$ of free variables under $\sigma=\phi\rho$ has expectation $m$. Chernoff bounds give $v \in[m/2,2m]$ except with probability at most $2e^{-m/8} \le2\cdot2^{-m/8}$.

Fix a restriction whose number of free variables lies in this interval. First translate the target by a uniform element of $W$; its offset becomes uniform in $V$. In Theorem 4.2 take $t=4L$ and threshold $\beta=2^{-v/8}$. Union over fewer than $2^{vL+1}$ list tests and use $(2t-1)!!\le(2t)^t$. Their simultaneous failure probability is at most

because $v\ge8\log(8L)$. The list-length bound $L$ dominates $L_{512}(v,b)$. On success, Theorem 2.1 and Eqn. (13) imply

The second term of Eqn. (20) is at most $128L2^{-3N/16}$, since $b_0\le N/4$ and $2vL\le4mL\le N/16$. The first is at most $2^{1-3mL/4}$.

We now remove the translation average. Translation within $W$ flips the unfixed binary coordinates of $V$. It preserves the product distribution of random restrictions and maps the class of all width-$b$ CNFs on the surviving bits to itself. Thus the bad-event probability just bounded is the same for each fixed translate of the target. Its average bound holds for the untranslated target as well. This does not say that every small subcube is good. It gives a joint good event for $(\phi,\rho)$ under their unconditional product distribution. Apply Theorem 3.2. □

The case $V=E$ will suffice for worst-case hardness. The uniformity over initial subcubes of codimension up to $N/4$ is needed to remove the restriction on bottom fan-in in the correlation argument.

Controlling the whole circuit

We first work at a tower length $N$ with $f=(-1)^{I_N}$. Since inversion permutes $E$ and trace is a nonzero linear functional, $\mathbb{E}f=0$. Consequently, for Boolean $C$,

We prove bounds on the right, including bounds on subcubes where $f$ need not be balanced.

Guarded CNFs and common trees

Proof. Let $P_\lambda$ be the conjunction of literals specifying the root-to-leaf path. We call the product $P_\lambda H_\lambda$ a guarded CNF. A CNF leaf contributes $P_\lambda H_\lambda$. For a DNF leaf write its value as $1-H_\lambda$ with $H_\lambda$ a CNF, and contribute $P_\lambda-P_\lambda H_\lambda$. Extend residual functions by ignoring path coordinates. All atoms are width-$k$ CNFs, since a path is a conjunction of units. Paths partition the cube and each of at most $2^R$ leaves contributes at most two atoms. □

We use the following switching inputs. A width-$k$ CNF or DNF under a $p$-restriction has a decision tree of depth at most $t$ except with probability $(5pk)^t$ [9]. It then has both width-$t$ forms with at most $2^t$ terms or clauses. Håstad’s multi-switching lemma [10], in the formulation of Tal [22 Definition 14 and Lemma 15], states that a family of $M$ depth-two circuits of bottom fan-in at most $k$ has, except with probability $M(24pk)^D$, a common $\lceil\log(2M)\rceil$-partial decision tree of depth at most $D$. At each leaf, each member has an ordinary decision tree of the stated residual depth. We use the constant 24 from the cited formulation.

Here and below, circuits are initially alternating and layered. Constants and unary gates are retained, and original layer labels are retained under cofactors. These conventions keep the circuit class closed under the operations in the proof. Section C normalizes general circuits at polynomial size cost.

The full construction is in Section A. Its key feature is that $s$ switching stages use fixed survival probabilities $\Theta_d(1/\ell)$. With common trees the depth bound at stage $i$ pays for all previous leaves, yet the final tree depth stays at most $(2^s-1)D_0$. Theorem 5.1 then gives Eqn. {(xref)}(5.3). At no point do we assert a product distribution of random restrictions after conditioning on a successful leaf.

Circuits with bounded bottom fan-in

Define

Take $b = \lfloor\log k/2048\rfloor$ and $p = b/(64k)$. On any initial subcube of codimension less than $N/4$, the expected number of free variables in Theorem 4.3 is

For a sufficiently small $c_* > 0$, uniformly in

the hypotheses in Eqn. {(xref)}(4.5) hold and

Indeed the list-length bound is $L = O_d(\ell^{1/4}\log\ell\log N)$, $m$ is at least a sufficiently large multiple of $\log\ell$, and $mL = o(N)$ even at $\ell= \log N$. Section B checks this uniformly, including both size endpoints.

When $m$ is at most a sufficiently large depth-dependent multiple of $\ell$, use Eqn. (22). Both its terms are $2^{-\Omega_d(m)}$. For larger $m$, choose $D_0 = \lfloor m/J\rfloor$ with $J$ a sufficiently large depth constant. Then $R_s \le m/4096$ and the failure term in Eqn. (23) is also $2^{-\Omega_d(m)}$. Combining the cases proves:

Removing the restriction on bottom fan-in

The following lemma replaces an additive truncation error by recursion through cofactors. It is useful precisely because Theorem 5.3 holds on every large initial subcube.

Apply the lemma with $k = k_0$ and $B = \lfloor N/4 \rfloor$. Then $a_0 < 1/2$ and the second hypothesis holds. Theorem 5.3 yields

Here $\mathcal{R} = o(N)$ uniformly over the range in Eqn. (24), and its minimum in that range tends to infinity. This proves the correlation estimate for layered circuits at tower lengths. Circuit normalization costs $O_d(S_0^3)$ gates, which we absorb using budget $S = S_0^3$. Eqn. (21) and padding from $N$ to $n < 2N$ change only depth-dependent constants. The uniform field construction, normalization, and padding details are in Section C; they complete Theorem 1.2.

Worst-case hardness through monochromatic covers

For exact computation we can stop depth reduction one layer earlier. We use Håstad’s depth reduction in the form stated by Chukhin [3 Lemma 2.3]: for fixed $d \ge3$ and $S \ge M \ge2$, there are common parameters

such that a $q$-restriction of a size-$S$, depth-at-most-$d$ circuit with OR output is an OR of at most $S^{A_d}$ width-$k$ CNFs with probability at least $3/4$. The same parameters work for all such circuits on $M$ bits.

A CNF is monochromatic for a target if the target is constant on its set of satisfying assignments.

Proof. Complement all gates and literals if needed to give an OR output computing $G$ or $1-G$. On a successful depth reduction, the satisfying assignments of each top CNF lie in the corresponding level set of $G$. Its density equals its absolute correlation with $g_{\phi}$. Sum these densities over the at most $S^{A_d}$ children. On failure use one, then average $\phi$. Restriction averaging preserves the unconditional output density.

Inverse trace. At a tower length $N$, put $\ell= c(N \log N)^{1/(d-1)}$, $S = 2^\ell$, and

Then

Thus $mL = o(N)$, $m \gg\log L$, and $m \gg b$. Theorem 4.3 with $V = E$ gives

eventually. Since $I_N$ is balanced, Theorem 6.1 would imply

But $m/\ell= \Theta_d(c^{-(d-1)})$, so a sufficiently small $c$ makes the last term tend to zero. Padding proves the claim for $F_n$.

The other two targets. For the trilinear function, choose one coefficient slice using Chukhin’s restriction moments and union over our point-list tests. For the evaluator, fix an irreducible modulus for the analysis, use the original linear hash, and obtain $t$-wise independent signs by polynomial interpolation, where $t$ is the number of polynomial coefficients. In both cases the slice is selected before the circuit is chosen, and its two level sets each have density at least $1/3$. The common point-list transfer gives $\mathbb{E}_{\phi\kappa_k}(g_\phi) \leq5 \cdot2^{-\Omega(m)}$ at the scale in Eqn. (10). Theorem 6.1 finishes with $\delta= 1/3$. Section D gives the full moments, list counts, and input accounting. This completes Theorem 1.1.

Explicit upper bounds for inverse trace

We prove Theorem 1.3 by evaluating a product of Frobenius maps over an auxiliary field of polynomial size. Evaluation and interpolation over smaller fields are standard tools in constant-depth finite-field arithmetic [12]. The calculation below implements the arithmetic directly at the required Boolean depth, rather than first constructing a logarithmic-depth circuit and then compressing it. The qualitative existence of subexponential-size circuits at some fixed depth also follows from [12] for its explicit field representation; the depth allocations below are supplied here.

All circuits in this section are nonuniform. Field presentations, changes of basis, evaluation points, and lookup tables are fixed circuit data. The final circuits contain only unbounded-fan-in AND/OR gates and input negations. We count both gates and wires.

Enumerating intermediate states

Proof. For $k = 1$, use a full CNF or DNF on the $L$ input bits. Suppose $k \geq2$ and $1 \leq w < L$. Set $g = \left\lceil(L/w)^{1/k} \right\rceil$, and first assume $g \leq T$.

Split the block sequence into at most $g$ consecutive intervals of nearly equal length, and repeat this splitting for $k-1$ levels. To test a segment with a prescribed initial state and a prescribed final-state predicate, enumerate the states at its interval boundaries. For each boundary-state tuple, conjoin the corresponding interval tests; then take the OR over tuples. There are at most $2^{gw}$ tuples at a node. At a leaf, the segment has at most $\left\lceil T/g^{k-1}\right\rceil$ blocks, so its test has a full CNF on at most $L/g^{k-1}+b$ input bits.

Each interval test is again a computation of the same kind. Complementing its final-state predicate complements the test, so De Morgan’s law gives an AND-top implementation whenever an OR-top implementation is available, and conversely. At each internal node, choose AND-top circuits for the interval tests and merge their top gates with the conjunction for a boundary-state tuple. Each recursion level therefore adds one layer. Starting from depth two at the leaves gives total depth $k + 1$. Complementing the final predicate and applying De Morgan also gives both root types for both output polarities.

The number of levels is fixed. Counting copies, boundary tuples, and leaf truth tables bounds the logarithm of the size by

Here $gw = O_k(L^{1/k}w^{1-1/k} + w)$ and $L/g^{k-1} \le L^{1/k}w^{1-1/k}$. Leaf literal wires add only their input-length factor, and internal conjunctions add at most $g$ wires per tuple, so the same estimate covers wires.

For completeness, if $w \ge L$ or $T = 1$, the full truth table suffices. If $g > T$, then $(L/w)^{1/k} > T$, which gives $Tw < b$ for $k \ge2$. A single split into individual blocks has logarithmic size $O(Tw + b + \log(T + 2))$ and depth three, within the claimed bounds. This covers the rounding cases.

Representing inverse trace by evaluations

Let $E = \mathbb{F}_{2^N}$, with $N \ge2$, in any fixed binary basis. Fix a polynomial presentation $E \cong\mathbb{F}_2[Z]/(p)$, where $p$ is irreducible of degree $N$. For $1 \le j \le N - 1$, let $f_j(Z)$ be the degree-below-$N$ representative of $x^{2^j}$. Its coefficients are binary linear functions of the original input bits. Define

This polynomial has degree at most $D = (N - 1)^2$, and

because $\sum_{j=1}^{N-1} 2^j = 2^N - 2$. The identity also holds at zero. Reduction modulo $p$ followed by trace is a fixed binary linear functional of the coefficients of $P_x$; denote it by $\Lambda$.

Put $M = D + 1$ and choose an auxiliary field $K = \mathbb{F}_{2^s}$ with $s = \lceil\log M\rceil$. Choose $M$ distinct points $\alpha_1, \ldots, \alpha_M \in K$. The auxiliary field need not embed in $E$. Interpolation determines $P_x$ from the values

To extend $\Lambda$ to the coefficients obtained by interpolation over $K$, choose a binary linear map $\pi: K \to\mathbb{F}_2$ with $\pi(1) = 1$ and apply it to each coefficient before applying $\Lambda$. This agrees with $\Lambda$ on the actual polynomial, whose coefficients lie in $\mathbb{F}_2$. The resulting map from $K^M$ to $\mathbb{F}_2$ is binary linear, so there are fixed binary linear functionals $\lambda_\ell: K \to\mathbb{F}_2$ such that

In particular, the final parity has $M = O(N^2)$ scalar inputs.

Three stages at adjustable depths

Fix positive integers $h_1, h_2, h_3$ and a generator $\gamma$ of $K^\times$. For $y \ne0$, represent $\log_\gamma y$ by $s$ bits; assign logarithm zero to $y = 0$ and keep a separate zero flag. All logarithm and exponentiation tables are on $O(\log N)$ bits, so their descriptions have polynomial size.

Evaluation and logarithm tables. For every $j,\ell$, the map $x \mapsto f_j(\alpha_\ell)$ is a fixed binary linear map into $K$. A computation reading the $N$ raw input bits can accumulate its value in an $s$-bit state. Any chosen bit of its logarithm, or its zero flag, is a predicate of the final state. Applying Theorem 7.1 with $L=T=N$ and $b=1$ gives depth $h_1+1$ and logarithmic size

The polynomial number of required output bits adds only $O(\log N)$ to the logarithmic size. This stage includes all Frobenius maps and basis changes.

Multiplication at each evaluation point. For each $\ell$, read the $N-1$ logarithms and zero flags as blocks of $s+1$ bits. Maintain their logarithm sum modulo $|K|-1$ and the OR of the zero flags, using $s+1$ state bits. If a zero flag has occurred, output zero; otherwise the terminal predicate outputs $\lambda_\ell(\gamma^a)$, where $a$ is the accumulated sum. The transitions may be defined arbitrarily on invalid logarithm encodings, which do not arise from the first stage. Here $L=(N-1)(s+1)$ and $b=w=s+1$. Thus Theorem 7.1 gives depth $h_2+1$ and logarithmic size

There are only $M$ parallel computations. Although their formal inputs are correlated outputs of the first stage, the circuit is exact on every assignment to those formal inputs, so substitution is valid.

The final parity. Apply Theorem 7.1 to parity on the $M$ scalar outputs in Eqn. (28), using one state bit. This gives depth $h_3+1$ and logarithmic size

Proof of Theorem 1.3. Each stage has alternating gate layers and is available with either root type, for both output polarities. At a stage boundary, implement each input literal of the next stage by a circuit whose root type agrees with that next stage’s bottom gate. Merge the adjacent gates of the same type. Both polarities are available, so this introduces no internal negation. The two boundaries save one layer each, giving depth

Combining Eqns. (29)–(31) gives logarithmic size $O_h(\Phi_h(N))$. Gate sharing is allowed. Even if merging increases the wire count, the total number of distinct wires is at most quadratic in the number of gates and inputs before merging, which preserves this estimate.

The full DNF gives size $2^{O(N)}$ and depth two. Taking the best construction among the finitely many triples allowed at a fixed depth $d$ proves Eqn. (3). The allocations $(h_1,h_2,h_3)=(2,2,3)$ and $(2,2,4)$ give Eqn. (4); choosing $(h,h,2h)$ gives Eqn. (5). The case $N=1$ is immediate. Finally, $F_n$ ignores all but its first $N$ bits, where $N\le n<2N$, so the same circuits give the asserted bounds in $n$.

Thus inverse trace has exact circuits of size $2^{O(n)}$ at each fixed depth $d\ge8$. For every fixed $\varepsilon>0$, choosing an integer $h>1/\varepsilon$ in Eqn. (5) gives size $2^{O_\varepsilon(n^\varepsilon)}$ at depth $4h+1$. These estimates give sufficient depths and sizes; they do not establish optimality or exclude exponential hardness at depths three through seven.

Consequences and limits of the representation

The point-list theorem concerns descriptions of sets. It allows an exponential number of pieces, can require exact counts of satisfying assignments to find them, and permits many clauses per piece. Its use here is to make simultaneous probabilistic estimates possible. Section E derives a bound on the correlation of inverse trace with width-$k$ CNFs.

There is an intrinsic list-length cost. If $J=\operatorname{cl}_b(A)\ne\varnothing$, $1\le b\le m$, and $|A|\le L$, then every $b$-coordinate projection of $J$ has at most $L$ values. Shearer’s entropy inequality gives

Consequently any exact signed representation $\mathbf{1}_H=\sum_i c_i\mathbf{1}_{\operatorname{cl}_b(A_i)}$ with $|A_i|\le L$ satisfies

Section E proves both statements. For high-entropy $H$, coefficient mass $2^{\varepsilon m}$ forces $\log L\ge b(h/m-\varepsilon)$. Exponential dependence on width is therefore unavoidable for this dictionary.

In the inverse-trace union bound, the character-sum error term requires $mL=O(N)$. Together with Eqn. (32), this limits the useful width to logarithmic size. The worst-case proof also needs $m=\Omega_d(\log S)$. At depth three these constraints yield $\log S$ of order $\sqrt{N}\log N$; changing a constant in the partition cannot turn this argument into an exponential lower bound.

There is a separate higher-depth limitation of this covering route. If the outer restriction keeps each bit with probability $q$, then on any cube of free variables of dimension $v$ a singleton is a width-one CNF of absolute correlation $2^{-v}$ with any sign function. Hence

To make this smaller than $S^{-A_d}$ with $q=\Theta_d((\log S)^{-(d-3)})$ requires $(\log S)^{d-2}=O_d(N)$. This is a restriction on the method, not a general upper bound on circuit complexity. For the trilinear function a specific upper bound $2^{O_d(n^{2/d})}$ is known [3 Theorem 5.1], precluding truly exponential lower bounds at fixed $d\ge3$ for that target. For inverse trace, Theorem 1.3 rules out a size lower bound $2^{\Omega(n)}$ at every fixed depth $d\ge8$. It leaves open the corresponding question at depths three through seven, and its upper bounds remain above the lower-bound scale of Theorem 1.1. Distinguishing these upper bounds on the functions from limitations of the proof method is essential when assessing the remaining gap in Eqn. (6).

Acknowledgments

This work was carried out during the authors’ visit to the Simons Institute for the Theory of Computing. The authors thank the Institute for its hospitality and support during the program Pseudorandomness and High-Dimensional Expansion in Fall 2026.

AI disclosure. The authors initiated this project by investigating properties of the inverse-trace function relevant to circuit lower bounds. OpenAI Codex was used substantially, through iterative exchanges with the authors, to explore proof ideas and assist with exposition, proof auditing, and reference checking.

References

A Deterministic switching parameters

We prove Theorem 5.2, including its handling of shared gates and shallow leaves. Put $s=d-2$, $U_0=S$, and recursively set

These quantities depend only on $S,d$. Since $2^{t_i}\leq4U_{i-1}$,

In particular $U_i\leq2^{A\ell}$ for $A=6^d$.

At an active leaf of depth at least three, consider each second-layer subcircuit. Switching it to the opposite depth-two form permits its outer gate to merge with its parent, decreasing the whole circuit depth by one. An ordinary decision tree of depth at most $t_i$ supplies both forms with at most $2^{t_i}$ terms or clauses. Replacing all at most $U_{i-1}$ second-layer gates fits the size bound $U_i$. If a gate has several parents, all use the same replacement; only wires are duplicated. Each individual residual circuit therefore stays within $U_i$ gates.

A leaf already at depth at most two is frozen. It retains its current CNF or DNF under later random restrictions, without new tree queries. The maximum in the definition of $k_i$ ensures that this width remains allowed, including when $k_0>t_1$.

At every stage draw one fresh global $p_i$-restriction on all currently free coordinates, including variables absent from the simplified circuit. Continue drawing after any failure. The unconditional composition $\phi$ has restriction parameter

For fixed $d$, both $k=\Theta_d(\ell)$ and $q=\Theta_d(\ell^{-s})$ follow directly from these parameters.

The switching lemma

Condition on any successful prior history. At stage $i$, union over at most $U_{i-1}$ active second-layer functions. Its conditional failure probability is at most

After $s$ successful stages the output is a width-$k$ CNF or DNF. A CNF has correlation at most $\kappa_k$. A DNF equals $1-H$ with $H$ a width-$k$ CNF, and therefore has correlation at most $2\kappa_k$, because the constant-one test is also included. The restricted target need not be balanced. Use the Boolean bound one on failure and enlarge the successful expectation to the unconditional expectation over $\phi$. This proves Eqn. (22).

Common partial decision trees

Fix a positive integer $D_0$. Define

After stage $i-1$, maintain a restriction tree of depth at most $R_{i-1}$. Every active leaf has depth reduced by $i-1$, size at most $U_{i-1}$, and bottom fan-in at most $k_{i-1}$. Frozen leaves satisfy the same bounds.

Condition on earlier randomness. An old leaf has a fixed path restriction $\tau$. On coordinates outside $\operatorname{dom}\tau$, the next global random restriction is an independent $p_i$-random restriction. Apply the multi-switching lemma to the at most $U_{i-1}$ second-layer functions of that cofactor, requesting depth $D_i$ and residual depth at most $t_i$. Require this to succeed for every old leaf, even those that the new random restriction will make incompatible. A union bound over at most $2^{R_{i-1}}$ leaves gives conditional failure at most

Frozen leaves need no call.

Restrict the old tree by the global random restriction and delete incompatible paths. At each surviving active leaf splice in its new common tree, which queries only coordinates outside that old path. The resulting tree has depth at most $R_i$. Switching the residual depth-two functions to their opposite forms reduces circuit depth by one at each new leaf. The size and bottom fan-in bounds follow from Eqn. (A.1). This proves the induction.

Crucially, the $2^{R_{i-1}}$ factor is charged only to failure probability. It does not multiply the size of an individual leaf circuit or its bottom fan-in. We use a product distribution only for the unconditional composition of the global random restrictions in Eqn. (A.3).

Summing Eqn. (A.5) over $s$ stages bounds total failure by $s2^{A\ell-2D_0}$. On success, Theorem 5.1 bounds the final correlation by $2^{R_s+1}\kappa_k(g_V,\phi)$, even though its atoms depend on the full history. Enlarge to the unconditional expectation to obtain Eqn. (23).

Uniform parameter checks for average-case hardness

We give explicit depth constants to substantiate the uniform size range, rather than hide endpoint conditions in asymptotic notation. Let

The symbol $M_d$ here is a depth constant, not an input dimension. For all sufficiently large $N$, the deterministic bounds in Eqn. (A.1) satisfy

Assume Eqn. (24). For any subcube of codimension less than $N/4$, set

Uniformly in this range, eventually

The lower bound uses $\dim V \ge3N/4$ and Eqn. (B.1); the upper bound uses $\dim V \le N$ and $k \ge\ell$. In particular $k \ge b \ge2$ eventually, and the upper-size constant ensures $m \ge128\log\ell$.

For the list-length bound in Eqn. (17), $2^{512b} \le k^{1/4}$ gives

The last estimate uses $\ell\ge\log N$. Hence $m \ge16\log(8L)$ and $m \ge2b$. Also

This is uniform down to polynomial-size circuits: at $\ell=\log N$ and $d=3$ the upper bound is $O_d((\log\log N)^2/(\log N)^{3/4})$. Thus $mL\le N/64$ eventually. Furthermore $m=o(N)$ uniformly, and $L$ is polynomially bounded in $N$.

All terms in $\Delta$ in Eqn. (19) are eventually bounded by a constant multiple of $\gamma=2^{-3m/64}$: the two dimension-tail contributions and the paired term have stronger exponents in $m$, and $128L2^{-3N/16}$ is exponentially smaller since $m=o(N)$. In particular Eqn. (25) follows.

If $m<M_d\ell$, Eqns. (22) and (25) give

If $m\ge M_d\ell=4JA\ell$, set $D_0=\lfloor m/J\rfloor$. For large $N$, $m\ge2J$ and

The multi-switching estimate gives

Since $m\to\infty$ uniformly and $\zeta=1/(16M_d)$ is smaller than the displayed decay constants, both cases are at most $2^{-\zeta m}$ eventually. Using $m\ge a\mathcal{R}$ proves Theorem 5.3 with $\theta_d=\zeta a$.

Finally, $\mathcal{R}/N=\log\ell/\ell^{d-1}\to0$ uniformly. For large $\ell$ the function $\log\ell/\ell^{d-1}$ decreases, so its minimum over the range in Eqn. (24) is at the upper endpoint, where $\mathcal{R}\ge c_*^{-(d-1)}\log\ell\to\infty$. This justifies absorbing fixed factors and the cofactor-recursion remainder into a smaller exponent constant.

Uniform fields, general circuits, and padding

A deterministic field tower

Start with $E_0=\mathbb{F}_2$ and $\gamma_0=1$. Recursively define

Inductively $\gamma_{j-1}$ has absolute trace one. In a binary field, $z\mapsto z^2+z$ has kernel $\{0,1\}$ and its image is the trace-zero subspace. Indeed trace vanishes on its image, and both spaces have codimension one. Therefore the displayed quadratic is irreducible. Its roots differ by one, so $\operatorname{Tr}_{E_j/E_{j-1}}(\theta_j)=1$. It follows that

Thus $E_j$ has binary dimension $N=2^j$. The recursive pair basis is deterministic. Multiplication uses at most five multiplications in the previous field and a linear number of bit additions, so its complexity is polynomial in $N$. Inversion by $x^{2^N-2}$ for $x\ne0$, and trace by $N$ Frobenius iterates, are also polynomial time. No search for irreducible polynomials is needed. The finitely many small input lengths can be defined by the same inverse-trace rule.

Layering a circuit without increasing its depth

Let a general circuit have size $S_0 \ge N$ and depth at most $d$. First bypass paths of consecutive same-type gates by connecting each parent directly to its same-type descendants’ frontier inputs. Retain a shared gate when it is still used by an opposite-type parent. This preserves the Boolean function without adding gates or increasing depth. Every remaining internal wire joins opposite gate types.

All gate-to-output path lengths from a given gate have parity determined by its type. Assign that gate its longest such path level. An internal wire skips a positive odd number of levels. Fill the skipped levels with alternating unary gates; similarly pad literal-to-gate wires. There are $O((S_0+N)^2)$ distinct wires and $d$ is fixed, so this adds $O_d(S_0^2)$ gates and does not increase depth. Unused layers, constants, and unary gates may be retained. This representation supports the fixed layer labels used in cofactor recursion.

For sufficiently large $S_0$, the deterministic budget $S=S_0^3$ dominates the normalized size. With $\ell=3\log S_0$, the previous estimates apply for

Changing $\log S_0$ to $3\log S_0$ alters $N\log\log S_0/(\log S_0)^{d-1}$ by depth-dependent constant factors. Eqn. (21) absorbs the factor two in passing to sign correlation.

A single family at all lengths

For arbitrary $n$, let $N$ be the largest power of two at most $n$, and define $F_n$ to evaluate $I_N$ on its first $N$ input bits. Ignore the remaining bits. Then $N \le n < 2N$, and this is one uniform polynomial-time family, independent of $d,S$.

Fixing the ignored bits of an $n$-input circuit leaves a circuit on $N$ bits of no larger size or depth. The tower-length bound holds for every such fixing, so average and use the triangle inequality. Since $S \ge n \ge N$ and $N>n/2$, reducing the size constant by a factor $2^{1/(d-1)}$ and reducing the exponent constant by an absolute factor proves Theorem 1.2. For worst-case hardness, any exact circuit restricts to an exact circuit for $I_N$; moreover $N\log N=\Theta(n\log n)$. This proves the padded part of Theorem 1.1. No pseudorandomness under translations in ignored directions is asserted or needed.

The two parameterized worst-case targets

The trilinear function

Write $g_z=(-1)^{T_a(\cdot,\cdot,z)}$. We use the following two results of Chukhin [3 Lemmas 4.2 and 4.3]. If $T_y\subseteq\{0,\ldots,a-1\}$ includes each index independently with probability $m/a$, where $m\le a^{3/5}$ and $u\le m^{1/4}$, then except with probability $a^{-\Omega(m)}$,

If a fixed data restriction has $|T_x|\ge2u$, $u$ even, and $|B+T_y|\ge|B||T_y|/2$ for those $B$, then for every fixed Boolean indicator $J$ on the cube of free variables,

The indicator can be arbitrary; a clause description is not needed for this moment input.

Proof. Put $\varepsilon= 2^{-m/32}$ and draw the fresh inner $p$-restriction. The numbers of free variables in the two blocks are in $[m/2,2m]$ except with probability at most $2\varepsilon$ eventually. Eqn. (D.1) fails with probability at most $\varepsilon$. Outside these events, the total number of free variables $v$ lies in $[m,4m]$, the sumset hypothesis of Eqn. (D.2) holds, and $|T_x| \ge2u$.

Markov’s inequality at threshold $2^{-m/16}$ bounds the failure probability for any fixed list test by $2^{1-um/16}$. Union over fewer than $2^{vL_*+1}$ tests to get

eventually. On success, Theorem 2.1 with $C = 2048$ gives for every width-$b$ CNF $H$

The joint failure probability over $z$, $\phi$, $\rho$ is at most $4\varepsilon$. Averaging fixes one $z$ with failure probability at most $4\varepsilon$. Theorem 3.2 then gives $5\varepsilon$.

To finish the lower bound, fix $d \ge3$ and let

Use the worst-case depth-reduction parameters $k,q$ from § 6. For small fixed $c_d > 0$, $k \ge b$ eventually, and

Then $m \le a^{3/5}$ and

Theorem D.1 applies. The constant-one CNF and restriction averaging give $|\mathbb{E}g_z| \le5\cdot2^{-m/32}$, so both level sets of the selected slice have density at least $1/3$. Theorem 6.1 would imply

Since $m/\ell= \Theta_d(\eta c_d^{-(d-1)})$, sufficiently small $c_d$ gives a contradiction. The total input length is $4a-1$, proving the trilinear part of Theorem 1.1.

The original polynomial evaluator

We spell out the family to avoid changing its input accounting or hiding its parameter inputs. At total input length $n$, let $a=\lfloor n/5\rfloor$, $r=\lceil a^{2/3}\rceil$, and let $t$ be the largest nonnegative even integer at most $a^{1/6}$. Reject if $a<64$ or if the following blocks do not fit. Otherwise parse:

• $a$ data bits $x_1,\ldots,x_a$ and $a+r-1$ hash bits $u_1,\ldots,u_{a+r-1}$;

• $r$ bits specifying the monic modulus $P(Z)=Z^r+\sum_{i<r}p_iZ^i$;

• $tr$ coefficient bits specifying $\beta_0,\ldots,\beta_{t-1}$ in $R_P=\mathbb{F}_2[Z]/(P)$.

Their total is $2a+(t+2)r-1\le n$ for all sufficiently large lengths. Ignore unused bits. Form

Let $\lambda$ select the degree-zero coefficient. The evaluator accepts exactly when

This is the original family of [19]. Ring operations are defined for every monic input modulus, whether reducible or not, and the algorithm runs in polynomial time. No irreducibility search is part of computing the function.

For hardness analysis choose one irreducible modulus of degree $r$. For every nonzero difference $w$ of data inputs, the hash $h(w)$ is uniform over $\mathbb{F}_2^r$ when $u$ is uniform. To see this, let $s$ be the largest coordinate with $w_s=1$. Row $i$ has the fresh pivot $u_{i+s-1}$, with all other indices smaller, so the $r$ rows are independent linear forms in $u$. A $v$-dimensional coordinate subcube has at most $2^v-1$ nonzero differences; the hash fails to be injective on it with probability at most $2^{v-r}$.

Conditioned on an injective hash, evaluation at any at most $t$ distinct hashes maps uniform coefficients to independent uniform field values. This follows from Lagrange interpolation with polynomials of degree at most $t-1$. Applying the nonzero coordinate functional $\lambda$ gives unbiased $t$-wise independent signs $g$ on the cube of free variables. For any fixed indicator $J$, expand the even $t$th moment of $Y=\sum_z g(z)J(z)$. A tuple with a singly occurring point contributes zero. The remaining tuples have at most $t/2$ distinct points and are covered by at most $2^{vt/2}t^t$ descriptions. Therefore

This argument derives the moment directly for arbitrary indicators; it does not invoke a source proposition outside its fixed-width quantifiers.

For an expected number of free variables $m$, set

For $v\in[m/2,2m]$, union over fewer than $2^{vL_*+1}$ tests. By Eqn. (D.3), failure is at most $2^{-v t/8}$ whenever

Indeed these bounds leave the total positive exponent at most $3vt/32<vt/8$. On success, the $C=512$ point-list partition gives $\kappa_b(g)\le2^{v/32}2^{-v/4}\le2^{-v/8}$. If $r\ge(2+1/16)m$, the hash error is at most $2^{-m/16}$. Each dimension tail is also at most $2^{-m/16}$. Thus joint failure is at most $4 \cdot2^{-m/16}$ eventually. Averaging fixes all non-data inputs before selecting any circuit or test, and Theorem 3.2 gives a slice with

Finally choose $b = \lfloor\log a/(64 \cdot512)\rfloor$, $\ell= c_d(a \log a)^{1/(d-1)}$, and the worst-case parameters $k,q$, $p = b/(64k)$. Then

All preceding conditions hold. The constant-one test gives output densities at least $1/3$. Theorem 6.1 contradicts exact computation by size $2^\ell$ when $c_d$ is sufficiently small. Since $a = \lfloor n/5\rfloor$, this proves the evaluator part of Theorem 1.1 in total input length, with its original parameters unchanged.

Further consequences of the decomposition

Bounded-width CNFs and monochromatic sets for inverse trace

Proof. Use Theorem 4.3 with $q = 1$ and $V = E$, so $m = Nb/(64k)$. Its list-length bound obeys

uniformly in the stated range. This gives $mL \leq N/64$ eventually. For $k \geq\sqrt{N}$, the upper endpoint gives $m \geq64C_0b$, while $\log(8L) \leq2C_0b$ eventually. For $k < \sqrt{N}$, $m \geq\sqrt{N}b/64 \gg\log L$. Thus the remaining hypotheses hold. The terms of $\Delta$ are bounded by four times $2^{-3m/64}$ eventually. For a monochromatic CNF $H$, we have $\lvert\mathbb{E}[fH]\rvert= \Pr[H = 1]$.

The intrinsic list-length requirement

Proof. For $X$ uniform on $J$, each projection $X_U$, $\lvert U\rvert= b$, has entropy at most $\log L$. Expand every $H(X_U)$ in coordinate order. Conditioning on only $U \cap[i-1]$ cannot reduce the conditional entropy below $H(X_i \mid X_{[i-1]})$. Each coordinate appears in $\binom{m-1}{b-1}$ subsets, whence

For a signed representation, sum its pointwise absolute upper bound over the cube:

Comparison with the Fourier-tail bound

For a binary character $\chi_\xi(x)=(-1)^{\langle\xi,x\rangle}$, nondegeneracy of the trace pairing supplies $a\in E$ with $\chi_\xi(x)=\psi(ax)$. The case $h=1$ of Theorem 4.1 gives

For a sign-valued depth-$d$ circuit $G$ of size $S$, Tal’s Fourier-tail theorem [22 Theorem 1] gives, for a depth constant $A_d$,

Take $k=\lfloor N/100\rfloor$. The Fourier mass of $f$ below $k$ is at most

Split Parseval’s identity at $k$ and apply Cauchy–Schwarz to each part. Using the fact that each sign function has total Fourier mass one gives

This is $2^{-\Omega_d(N/(\log S)^{d-1})}$ when that exponent tends to infinity, with the displayed estimate valid also outside that regime. Padding works as in Section C. The higher shift moments, point-list decomposition, and guarded-CNF argument supply the additional $\log\log S$ factor in Theorem 1.2.