1 · The essentials
The manuscript describes a yes-or-no task on strings of bits that a deterministic algorithm can solve in polynomial time. It asks how large a different kind of computing device must be to give the same answers. These devices have three layers of gates: OR, then AND, then OR, with no fixed limit on how many inputs a gate can receive. The constructed task requires more gates than for every fixed positive constant , once the input length is sufficiently large. This requirement applies at every sufficiently large length, not just at occasional lengths. It counts all gates, including those in the bottom layer. The main result has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine answering a checklist through three rounds: groups first report whether any item passes, the next round checks whether all required reports pass, and the last round accepts if any remaining report passes. The result says that one efficiently answerable task needs an exceptionally large number of such checks when forced into precisely this three-round arrangement; the image does not capture the exact mathematical growth rate.
Why it matters
The source identifies the result as crossing the square-root-exponent threshold for explicit depth-three Boolean circuit lower bounds. It distinguishes what a deterministic polynomial-time algorithm can do from what this particular three-layer circuit arrangement can do with a limited number of gates. Counting the bottom layer makes the statement a bound on the entire circuit, rather than only part of it.
2 · Going further
The precise object is a single language in deterministic polynomial time. For each input length , its membership function answers whether an -bit string belongs to . The main result states that computing this function with an unbounded-fan-in OR–AND–OR circuit requires total gates, at every sufficiently large input length.
The notation means that the exponent grows faster than every constant multiple of : equivalently, the required size eventually exceeds for every fixed . The gate count includes the bottom layer. Thus both the precise circuit arrangement and the choice to count all gates are essential parts of the statement.
The repository summary describes this as crossing the square-root-exponent threshold for explicit depth-three Boolean circuit lower bounds. The supplied abstract announces the construction and lower bound but does not describe the construction or the argument establishing the bound, so no argument outline can be recovered from this source. Only the main manuscript is supplied; no companion manuscripts or relationships between them are described. The main result is identified as Lean-formalized, although the supplied text gives no further details about the formalization's scope.
Useful notions
- Bit strings and yes-or-no functions
- AND and OR gates
- Circuit layers and gate counts
- Deterministic polynomial time
- Asymptotic growth notation
What was known before / what is new
Before
The source names the square-root-exponent threshold as the benchmark for explicit depth-three Boolean circuit lower bounds. It does not provide earlier bounds, historical attributions, or details about previous constructions.
New
The manuscript constructs a single deterministic polynomial-time language with a lower bound for unbounded-fan-in OR–AND–OR circuits. The bound holds at every sufficiently large input length and counts every gate, including the bottom layer. The main result has a Lean formalization.
Limits and assumptions
The lower bound concerns the specified unbounded-fan-in OR–AND–OR circuit model; the source does not state a corresponding bound for other circuit arrangements. It applies to the constructed language and to every sufficiently large input length, not necessarily to smaller lengths. The main result is Lean-formalized, but no finer account of the formalization's coverage is supplied. The abstract gives neither the argument nor a list of remaining open questions.
Mini glossary
- Language —
- A set of bit strings, with membership giving a yes-or-no answer for each string.
- Deterministic polynomial time —
- A computation with no random choices whose running time is bounded by a polynomial in the input length.
- Unbounded fan-in —
- A circuit convention that places no fixed limit on the number of inputs a gate can receive.
- OR–AND–OR circuit —
- A three-layer Boolean circuit with a bottom layer of OR gates, a middle layer of AND gates, and a top layer of OR gates.
- Circuit lower bound —
- A requirement that every circuit in a specified model computing a given function must have at least a stated size.
- —
- A growth rate that eventually exceeds for every fixed positive constant .
Keywords : Circuit lower bounds · Depth-three circuits · Polynomial-time languages
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Constructs a single language in deterministic polynomial time whose n-bit membership function requires total gates in unbounded-fan-in OR–AND–OR circuits, at every sufficiently large input length. This crosses the square-root-exponent threshold for explicit depth-three Boolean circuit lower bounds.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits
23/09/2026We construct a language in deterministic polynomial time whose n-bit membership function requires gates in an unbounded-fan-in OR–AND–OR circuit. The bound holds at every sufficiently large input length and counts all gates, including the bottom layer.