Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-167 | 6th September 2026 01:11

Almost-Everywhere Near-Cubic Wire Lower Bounds for SYM $\circ$ THR and THR $\circ$ THR

RSS-Feed




TR26-167
Authors: Dev Nag
Publication: 6th September 2026 02:51
Downloads: 29
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint