We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{\Omega(1)}} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [22].

We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential- time learning algorithms for AC0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth.

Our techniques include adaptive random restrictions, anti-concentration and the structural theory of threshold functions, and bounded-read Chernoff bounds.