# Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 49 references that are in the map.
- First posted on arXiv 1 Jul 2021.

## Builds on (most cited first, 5 of 5)

- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits](https://mlsanity.com/paper/1511.07860/) (2015)
- [Unsupervised Feature Learning by Deep Sparse Coding](https://mlsanity.com/paper/1312.5783/) (2013)
- [A Basic Compositional Model for Spiking Neural Networks](https://mlsanity.com/paper/1808.03884/) (2018)

## Abstract (arXiv)

In this paper, we investigate computational power of threshold circuits and other theoretical models of neural networks in terms of the following four complexity measures: size (the number of gates), depth, weight and energy. Here the energy complexity of a circuit measures sparsity of their computation, and is defined as the maximum number of gates outputting non-zero values taken over all the input assignments. As our main result, we prove that any threshold circuit C of size s, depth d, energy e and weight w satisfies log (rk(MC)) ≤ ed (log s + log w + log n), where rk(MC) is the rank of the communication matrix MC of a 2n-variable Boolean function that C computes. Thus, such a threshold circuit C is able to compute only a Boolean function of which communication matrix has rank bounded by a product of logarithmic factors of s,w and linear factors of d,e. This implies an exponential lower bound on the size of even sublinear-depth threshold circuit if energy and weight are sufficiently small. For other models of neural networks such as a discretized ReLE circuits and decretized sigmoid circuits, we prove that a similar inequality also holds for a discretized circuit C: rk(MC) = O(ed(log s + log w + log n)3).