For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed by any depth-$d$ $\text{TC}^0$ circuit with $n^{1 + \gamma}$ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth $d > 2$, which were previously known only for functions outside $\text{AC}^0$ such as the parity function. Furthermore, in our result, the $\text{AC}^0$ circuit computing $F$ is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage $n^{-\gamma}$.

At a high level, our proof strategy combines two prominent approaches in circuit complexity from the last decade: The celebrated *random projections* method of Håstad, Rossman, Servedio, and Tan (J. ACM 2017), which was previously used to show a tight average-case depth hierarchy for $\text{AC}^0$; and the line of works analyzing the effect of *random restrictions* on threshold circuits. We show that under a modified version of Håstad, Rossman, Servedio, and Tan’s projection procedure, any depth-$d$ threshold circuit with $n^{1 + \gamma}$ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth $d + 1$ maintains structure.

Revised exposition.

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed by any depth-$d$ $\text{TC}^0$ circuit with $n^{1 + \gamma}$ wires. This bound matches the current state-of-the-art lower bounds for computing explicit functions by threshold circuits of depth $d > 2$, which were previously known only for functions outside $\text{AC}^0$ such as the parity function. Furthermore, in our result, the $\text{AC}^0$ circuit computing $F$ is a monotone *read-once formula* (i.e., an AND-OR tree), and the lower bound holds even in the average-case setting with respect to advantage $n^{-\gamma}$.

Our proof builds on the *random projection* procedure of Håstad, Rossman, Servedio, and Tan, which they used to prove the celebrated average-case depth hierarchy theorem for $\text{AC}^0$ (J. ACM, 2017). We show that under a modified version of their projection procedure, any depth-$d$ threshold circuit with $n^{1 + \gamma}$ wires simplifies to a near-trivial function, whereas an appropriately parameterized AND-OR tree of depth $d + 1$ maintains structure.