# Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2018.

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

- [On the Complexity of Neural Computation in Superposition](https://mlsanity.com/paper/2409.15318/) (2024)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Neural Sculpting: Uncovering hierarchically modular task structure in neural networks through pruning and network analysis](https://mlsanity.com/paper/2305.18402/) (2023)
- [Spiky Rank and Its Applications to Rigidity and Circuits](https://mlsanity.com/paper/2602.23503/) (2026)

## Abstract (arXiv)

We consider the problem of representing Boolean functions exactly by "sparse" linear combinations (over ℝ) of functions from some "simple" class cal C. In particular, given cal C we are interested in finding low-complexity functions lacking sparse representations. When cal C is the set of PARITY functions or the set of conjunctions, this sort of problem has a well-understood answer, the problem becomes interesting when cal C is "overcomplete" and the set of functions is not linearly independent. We focus on the cases where cal C is the set of linear threshold functions, the set of rectified linear units (ReLUs), and the set of low-degree polynomials over a finite field, all of which are well-studied in different contexts. We provide generic tools for proving lower bounds on representations of this kind. Applying these, we give several new lower bounds for "semi-explicit" Boolean functions. For example, we show there are functions in nondeterministic quasi-polynomial time that require super-polynomial size: bullet Depth-two neural networks with sign activation function, a special case of depth-two threshold circuit lower bounds. bullet Depth-two neural networks with ReLU activation function. bullet ℝ-linear combinations of O(1)-degree mathbbFp-polynomials, for every prime p (related to problems regarding Higher-Order "Uncertainty Principles"). We also obtain a function in ENP requiring 2Omega(n) linear combinations. bullet ℝ-linear combinations of ACC circ THR circuits of polynomial size (further generalizing the recent lower bounds of Murray and the author). (The above is a shortened abstract. For the full abstract, see the paper.)