# Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

arXiv: https://arxiv.org/abs/1511.07860 · HTML: https://mlsanity.com/paper/1511.07860/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Nov 2015.

## Built on by (most cited first, 6 of 6)

- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Pause Tokens Strictly Increase the Expressivity of Constant-Depth Transformers](https://mlsanity.com/paper/2505.21024/) (2025)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy](https://mlsanity.com/paper/2107.00223/) (2021)
- [Spiky Rank and Its Applications to Rigidity and Circuits](https://mlsanity.com/paper/2602.23503/) (2026)

## Abstract (arXiv)

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. bullet We prove that for all εgg √log(n)/n, the linear-time computable Andreev's function cannot be computed on a (1/2+ε)-fraction of n-bit inputs by depth-two linear threshold circuits of o(ε3 n3/2/log3 n) gates, nor can it be computed with o(ε3 n5/2/log7/2 n) wires. This establishes an average-case ``size hierarchy'' for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of o(n3) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates. bullet We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two linear threshold circuits with o(n3/2/log3 n) gates, nor with o(n5/2/log7/2n) wires. bullet We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.