Beyond the square-root exponent for depth-three circuits

← All digests

Family 112 · Theoretical computer science
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-09

A calculation can be easy when performed through many successive steps and expensive when forced into only three layers of logic. Family 112 claims an explicit example of this phenomenon beyond a longstanding quantitative threshold. The result concerns a restricted circuit architecture, while allowing that architecture unrestricted fan-in, shared gates, and a separate design for every input length.

1. The question

A Boolean circuit computes a function of bits by connecting logical gates. An AND gate outputs one when all its inputs are one; an OR gate outputs one when at least one input is one.

The circuits here have three layers: OR gates at the bottom, AND gates in the middle, and an OR gate at the top. Every bottom gate may read arbitrarily many input literals, where a literal is a bit or its negation.

Can a function that is efficiently computable by an ordinary algorithm nevertheless require an enormous number of gates in this shallow architecture? Classical examples already require roughly a square-root exponential, of the form $2^{c\sqrt n}$ for a fixed positive constant $c$.

The manuscript asks for one polynomial-time language whose required circuit size eventually exceeds $2^{A\sqrt n}$ for every fixed constant $A$. The function must be explicit and efficiently evaluable; merely counting how many difficult Boolean functions exist would not suffice.

2. Background and essential definitions

Languages and their membership functions

A language $L\subseteq\{0,1\}^*$ is a set of finite binary strings. For each length $n$, its membership function $f_n$ takes an $n$-bit string and outputs one exactly when the string belongs to $L$.

Saying $L$ is in deterministic polynomial time means one fixed algorithm decides membership in at most $C(n+1)^a$ steps, for fixed constants $C,a$. The algorithm works across all lengths.

By contrast, the circuits may be nonuniform: a different circuit can be chosen independently for each $n$, with no requirement that an efficient algorithm construct it. This makes a lower bound stronger than one restricted to efficiently generated circuit families.

Clauses and three-layer circuits

A clause is an OR of literals, such as $x_1\lor\neg x_3\lor x_7$. A conjunction of clauses is a formula in conjunctive normal form, abbreviated CNF.

An OR–AND–OR circuit is therefore an OR of CNFs. The width of a clause is the number of variables it contains. Width is unrestricted in the target circuit model.

Let $S_3(f)$ be the smallest total number of AND and OR gates needed to compute $f$ in this model. All three layers count, including bottom clauses and the top output gate. Input negations are free, and gates may feed several later gates.

Counting only the number of middle CNFs would be misleading: every Boolean function has some CNF representation, although that CNF may contain exponentially many clauses. The total gate budget prevents those clauses from being treated as free.

Reading the growth rate

The notation

$$S_3(f_n)=2^{\omega(\sqrt n)}$$

uses the asymptotic symbol $\omega$, meaning growth faster than every constant multiple in the exponent. It is unrelated to the matrix multiplication exponent in family 107.

Precisely, the assertion is

$$\lim_{n\to\infty}\frac{\log_2 S_3(f_n)}{\sqrt n}=\infty.$$

This is stronger than one bound $2^{c\sqrt n}$, but weaker than a bound $2^{n^{1/2+\varepsilon}}$ for some fixed $\varepsilon>0$. An unbounded multiplier of $\sqrt n$ could grow much more slowly than any positive power of $n$.

3. Development history and previous partial results

Håstad’s random-restriction and switching methods established major lower bounds for constant-depth circuits. A random restriction fixes many input bits and leaves the others free. A shallow circuit often simplifies dramatically under such a restriction, while the target function retains enough difficulty to force a large original circuit.

For parity—the function recording whether the number of one bits is odd—the depth-three lower-bound exponent has square-root order. Håstad, Jukna, and Pudlák developed a top-down approach and improved quantitative bounds for parity and majority.

Paturi, Pudlák, and Zane’s Satisfiability coding lemma, cited in M1, determined the depth-three parity scale sharply up to a constant factor in circuit size. Thus simply improving the analysis of parity cannot produce the desired unbounded multiplier in the exponent: parity itself has matching upper bounds at the older scale.

Connections with satisfiability algorithms also yielded lower bounds for code-membership functions. These remained within a constant times $\sqrt n$ in the leading exponent. Paturi, Pudlák, Saks, and Zane developed an important algorithmic route through isolated satisfying assignments.

Much stronger bounds are possible when bottom gates have bounded fan-in. Paturi, Saks, and Zane obtained nearly full exponential bounds in a bottom-fan-in-two setting. More recent local enumeration work treats related majority questions with small bottom width.

Those restrictions change the problem. Family 112 claims to cross the square-root-exponent threshold while leaving bottom fan-in unrestricted, and with one fixed polynomial-time language witnessing every required constant.

4. What the new manuscripts claim

M1 states that there is a language $L$, decided by one deterministic polynomial-time Turing machine, whose length-$n$ membership functions satisfy

$$\text{for every }A>0,\quad S_3(f_n)>2^{A\sqrt n} \quad\text{for every sufficiently large }n.$$

The threshold length may depend on $A$. The language and its polynomial-time membership algorithm do not.

The bound holds at every sufficiently large length, not merely infinitely many selected lengths. It counts all AND and OR gates, permits arbitrary sharing, and imposes neither a uniformity requirement nor a bottom-fan-in bound on the circuits being ruled out.

The theorem is about exact computation: the circuit must agree with the membership function on every input. Correlation estimates under random inputs are tools inside the argument, rather than a replacement of the theorem by an average-case statement.

The manuscript explicitly presents its conclusion as weaker than a fixed-power improvement $2^{n^{1/2+\varepsilon}}$. That stronger formulation should not be inferred from the notation.

5. Why the advance matters

Importance: 4/5, provisional. Explicit circuit lower bounds reveal limitations of computational architectures that are difficult to capture by ordinary algorithm analysis. Crossing a longstanding quantitative threshold for unrestricted depth-three circuits would be a substantial advance in these methods.

The result combines two kinds of strength. The target language remains efficiently computable by a general algorithm, while even nonuniform circuits in the specified shallow architecture require the claimed size. This isolates the cost of restricting depth rather than asserting that the underlying decision problem is generally intractable.

The conclusion does not separate $\mathsf P$ from $\mathsf{NP}$, since the constructed language is itself in $\mathsf P$. It instead shows that a fixed shallow form cannot efficiently express all computations that become possible with a longer sequence of steps.

6. The main idea

Make every middle gate cover very little

Represent a Boolean target function by a sign $g$, equal to plus one on accepted inputs and minus one on rejected inputs. For a CNF indicator $H$, consider its correlation

$$\left|\mathbb E[g(x)H(x)]\right|,$$

where $x$ is uniformly random.

If $H$ is one middle component of an exact OR representation, it cannot accept a negative input: that would make the whole circuit accept incorrectly. Consequently $gH=H$, so the correlation equals the fraction of inputs that component accepts.

If every admissible component has tiny correlation but the target accepts a substantial fraction of inputs, many components are needed to cover the target’s positive inputs. This is the basic counting mechanism behind the lower bound.

Simplify tests without losing control of their number

The circuit’s clauses may be wide. The manuscript develops a random-restriction statement expressing a restricted moderately wide CNF as a signed combination of constant-width CNFs.

“Signed” means some coefficients may be negative. The useful quantity is the sum of their absolute values, whose expectation is bounded under the chosen restriction parameters. Crucially, this bound does not grow with the original number of clauses.

Thus a function poorly correlated with every narrow CNF also remains poorly correlated with the wider tests relevant to the circuit. Exceptional restrictions and coefficient sizes are accounted for together, without assuming an independence that need not hold.

Put the hard choice into the input

The constructed language has a data block and parameter blocks. Its evaluator hashes the data and evaluates a polynomial in an algebraic quotient described by the parameters. These are operations a fixed polynomial-time machine can carry out.

For a desired lower-bound constant, probabilistic arguments establish a choice of parameter bits giving a hard function of the data block. The evaluator never has to search for this choice: it simply uses the parameter bits supplied in its input.

Fixing those bits selects a slice of the full membership function. If the full function had a small circuit, substituting those fixed values would also give a small circuit for that hard slice.

From narrow tests back to the full circuit

The paper uses sparsification to organize constant-width CNFs into controlled collections with few clauses. Limited-independence constructions and moment bounds then establish small correlations simultaneously across the relevant tests.

Very wide clauses in a small candidate circuit can be removed with a small total error under uniform inputs, because a clause of width $w$ is false on only a $2^{-w}$ fraction of assignments. Combining this truncation with the restriction argument shows that too few middle gates cannot cover the positive inputs.

The parameters used in this analysis vary with the desired constant $A$, while the language’s evaluator remains fixed.

7. Scope, limitations, and open questions

The lower bound applies to the stated OR–AND–OR architecture with free input negations. It should not be generalized to arbitrary depth, threshold gates, or unrestricted Boolean circuits.

It is also not a fixed positive-power improvement over the square-root exponent. Establishing such a rate remains beyond the claimed conclusion.

The hard slice is proved to exist within an explicit polynomial-time language. This does not mean the digest supplies an efficient algorithm that, given a lower-bound target, outputs the particular parameter choice witnessing it. The separation between easy evaluation and finding useful parameters is part of the construction.

8. Sources and further reading

M1’s first theorem states the quantifiers and gate-count convention precisely. Its introduction compares parity, code-membership, and bounded-bottom-width results. The linked historical papers explain why changing the target function and controlling clause count are both necessary to go beyond the older threshold.

Source manuscripts

• M1. OpenAI, Beyond the Square-Root Exponent for Depth-Three Boolean Circuits (September 23, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.