  $ \newcommand{\cclass}[1]{{\normalfont\textsf{##1}}} $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 a constant $\varepsilon_d > 0$ such that the Parity function on
$n$ bits has correlation at most $n^{-\varepsilon_d}$ with depth-$d$ threshold
circuits which have at most $n^{1+\varepsilon_d}$ wires, and the Generalized
Andreev function on $n$ bits has correlation at most
$\exp(-{n^{\varepsilon_d}})$ with depth-$d$ threshold circuits which have at
most $n^{1+\varepsilon_d}$ wires. Previously, only worst-case lower bounds in
this setting were known (Impagliazzo, Paturi, and Saks (SICOMP 1997)).
  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 on $n$ bits
cannot be computed by polynomial-size $\textsf{AC}^0$ 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 $\textsf{AC}^0$ 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 linear threshold functions, and bounded-read Chernoff
bounds.
