Superquadratic Lower Bounds for Depth-2 Linear Threshold Circuits

Proving lower bounds against depth-2 linear threshold circuits (a.k.a. THR • THR) is one of the frontier questions in complexity theory. Despite tremendous effort, our best lower bounds for THR • 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 ∈ E NP that requires n 2.5-ε -size THR • THR circuits for any ε > 0. We obtain our new results by designing a new 2 n-n Ω(ε) -time algorithm for estimating the acceptance probability of an XOR of two n 2.5-ε -size THR • THR circuits, and apply Williams' algorithmic method to obtain the desired lower bound.