Almost-Everywhere Near-Cubic Wire Lower Bounds for SYM ◦THR and THR ◦THR
Dev Nag · Zenodo (CERN European Organization for Nuclear Research) · 2026
This paper proves almost-everywhere near-cubic wire lower bounds against depth-two threshold circuit classes. For every fixed (c>0), it constructs a language in (E^{NP}) that, at every sufficiently large input length, cannot be approximated with agreement (1/2+n^{-c}) by (\mathrm{SYM}\circ\mathrm{THR}) circuits having (O(n^3/\log^{10}n)) wires or by (\mathrm{THR}\circ\mathrm{THR}) circuits having (O(n^3/\log^{12}n)) wires; at any fixed positive advantage, the denominators improve to (\log^5 n) and (\log^9 n). The proof develops a deterministic circuit-acceptance-probability algorithm whose cost depends on the wires touching a restricted set of live variables, combining exact residualization, multiscale counting polynomials, signed rectangular multiplication, hardness amplification, and an algorithm-to-lower-bound transfer.