TR26-039 | Super-quadratic Lower Bounds for Depth-2 Linear Threshold Circuits | Lijie Chen, Avishay Tal, Yichuan Wang

Proving lower bounds against depth-$2$ linear threshold circuits (a.k.a. $THR \circ THR$) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for $THR \circ THR$ only hold for sub-quadratic number of gates, which was proven a decade ago by Tamaki (ECCC TR16) and Alman, Chan, and Williams (FOCS 2016) for a hard function in $E^{NP}$. In this work, we prove that there is a function $f \in E^{NP}$ that requires $n^{2.5-\varepsilon}$-size $THR \circ THR$ circuits for any $\varepsilon > 0$. We obtain our new results by designing a new $2^{n - n^{\Omega(\varepsilon)}}$-time algorithm for estimating the acceptance probability of an XOR of two $n^{2.5-\varepsilon}$-size $THR \circ THR$ circuits, and apply Williams' algorithmic method to obtain the desired lower bound.