Kane and Williams proved average-case wire lower bounds at the $n^{5/2}/\mathrm{polylog}\, n$ scale for an explicit function against depth-two linear-threshold circuits, and Chen, Tal, and Wang recently proved worst-case gate lower bounds at the $n^{5/2-\delta}$ scale by the algorithmic method. Building on the restriction-and-analysis framework of Chen–Tal–Wang, we change the resource being charged from gates to wires and prove an almost-everywhere near-cubic wire lower bound for a language in $\mathrm{E}^{\mathrm{NP}}$. For every fixed $c>0$, there is one language $F_c$ and positive constants $b_{\mathrm{S},c}$ and $b_{\mathrm{T},c}$ such that, at every sufficiently large input length $n$, no $\mathrm{SYM}\circ\mathrm{THR}$ circuit with at most $b_{\mathrm{S},c}n^3/\log^{10}n$ wires and no $\mathrm{THR}\circ\mathrm{THR}$ circuit with at most $b_{\mathrm{T},c}n^3/\log^{12}n$ wires has agreement at least $1/2+n^{-c}$ with $(F_c)_n$. The same language works for both classes, and the gates may have arbitrary real weights. At any fixed positive advantage, the logarithmic denominators improve to $\log^5 n$ and $\log^9 n$.
The change of resource requires a change of accounting, not of architecture. A gate-count restriction analysis is fan-in-blind and becomes useless against many thin gates; we instead charge a restricted circuit by the number of input wires touching the live variables, so a wire budget is spent as a wire budget. Exact residualization removes both constant-zero and constant-one bottom gates from the algebraic population, collapsing all restriction advice to one scalar offset per column and making the analysis deterministic with zero bad columns. Multiscale counting polynomials and exact signed rectangular multiplication then give inverse-polynomially accurate analysis with an arbitrary fixed polynomial saving, and a componentwise Chen–Lyu–Williams transfer, its XOR contrapositive, and an exact length schedule yield the stated correlation lower bounds.
The text has been rewritten for readability, and the abstract and introduction now credit the restriction-and-analysis framework of Chen, Tal, and Wang (STOC 2026), on which this work builds. A frontier section (Section 9) and an interface index (Appendix D) were added. Theorems, lemmas, and their numbering are unchanged. Separately, Theorem 2.5 (the fixed-advantage bound) has been formally verified in Lean 4 from nine quoted statements of the cited results; the formalization required no changes to its proof: https://github.com/devnag/near-cubic-wires
Kane and Williams proved average-case wire lower bounds at the $n^{5/2}/\mathrm{polylog}, n$ scale for an explicit function against depth-two linear-threshold circuits. We prove an almost-everywhere near-cubic wire lower bound for a language in $\mathrm{E}^{\mathrm{NP}}$. For every fixed $c>0$, there is one language $F_c$ and positive constants $b_{S,c}$ and $b_{T,c}$ such that, at every sufficiently large input length $n$, no SYM $\circ$ THR circuit with at most $b_{S,c} n^3/\log^{10} n$ wires and no THR $\circ$ THR circuit with at most $b_{T,c} n^3/\log^{12} n$ wires has agreement at least $1/2+n^{-c}$ with $(F_c)_n$. The same language works for both classes, and the gates may have arbitrary real weights. At any fixed positive advantage, the logarithmic denominators improve to $\log^5 n$ and $\log^9 n$.
The algorithmic core is a deterministic circuit-acceptance-probability algorithm that charges a restricted circuit by the number of input wires touching the live variables, rather than by its number of bottom gates. Exact residualization removes both constant-zero and constant-one bottom gates from the algebraic population. Multiscale counting polynomials and exact signed rectangular multiplication then give inverse-polynomially accurate analysis with an arbitrary fixed polynomial saving. A componentwise Chen–Lyu–Williams transfer, its XOR contrapositive, and an exact length schedule yield the stated correlation lower bounds.
Several readers have voiced the following concerns, which seem correct to me.
1. It seems that the text was entirely generated by LLMs without much human effort.
In particular, it is extremely hard to read.
The ECCC board is determined not to allow this in the future,
and a statement reflecting this was added to the CFP.
2. The core of the result seems to be a reinterpretation of a recent paper due to Chen-Tal-Wang (STOC 2026) that combines random restriction and design of the CAPP algorithm (for Williams’s algorithmic approach). This paper seems to follow the same route, with the exception that it counts wires rather than gates (as Chen-Tal-Wang did). However, this is not mentioned at all in abstract, and not highlighted in introduction.
I thank Oded Goldreich, and the readers whose concerns he relayed, for engaging closely with this paper. Both concerns called for action; the original text was hard to read, and it did not credit Chen-Tal-Wang (STOC 2026) in the abstract or the introduction, as it should have. Three updates:
- Revised version (v2, 15 September 2026): https://zenodo.org/records/22773981. Rewritten for readability, it now credits Chen-Tal-Wang in the opening sentences of the abstract and throughout the introduction, and Section 1.2 sets the two papers side by side, listing what is inherited and what is new. As the new abstract says, moving from gates to wires is a change of accounting, not of architecture: a restricted circuit is charged by the input wires touching its live variables. The theorem numbering is unchanged from v1.
- Machine-checked proof in Lean 4: https://github.com/devnag/near-cubic-wires. Theorem 2.5, the fixed-advantage near-cubic wire lower bound, is derived in Lean from nine statements quoted from the cited papers. The proof has no sorry, uses only Lean's three standard axioms, and passes Lean's comparator check. The formalization required no changes to the paper's proof of this theorem. Checking the result reduces to the repository's nine SourceMapping pages, which quote each published statement verbatim with its PDF page, map it clause by clause to the Lean definitions, and list what a reader should check.
- Extension to exponent 7/2 (15 September 2026): "Wire-Correlation Tradeoffs at Exponent 7/2 for Depth-Two Threshold Circuits", https://zenodo.org/records/22774131. It proves almost-everywhere correlation lower bounds for depth-two threshold circuits, against a language in E^NP, at n^(7/2)/polylog(n) wires, raising the exponent from 3 to 7/2; as a corollary it gives gate lower bounds at n^(5/2)/polylog(n). The key idea is to replace coordinate restrictions with products of Hamming-code stars, so that each threshold gate is charged only for genuinely mixed dependence on the two live halves of a cell; with the sqrt(f) bound on the total influence of a threshold gate of fan-in f, the expected residual becomes O(W/n^(3/2)) up to logarithmic factors. A fixed-moment matrix sampler and a sparse masked verifier preserve this gain through deterministic counting and the Chen-Lyu-Williams transfer. That paper was written to be readable and to credit its sources from the start; it separates classical tools, inherited architecture, adapted interfaces, and new lemmas. Its formalization, reusing the same Lean development, is in progress.
Further comments and corrections are welcome.
