# Lower bounds over Boolean inputs for deep neural networks with ReLU gates

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2017.

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

- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation](https://mlsanity.com/paper/2102.06635/) (2021)
- [How Many Neurons Does it Take to Approximate the Maximum?](https://mlsanity.com/paper/2307.09212/) (2023)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Size and Depth Separation in Approximating Benign Functions with Neural Networks](https://mlsanity.com/paper/2102.00314/) (2021)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)
- [Shallower ReLU Network Representations via Exact Linear Algebra](https://mlsanity.com/paper/2607.21651/) (2026)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)
- [Representation Costs in Data Science: Foundations and the Quasi-Banach Spaces of Deep Neural Networks](https://mlsanity.com/paper/2606.14954/) (2026)
- [VC dimension of partially quantized neural networks in the overparametrized regime](https://mlsanity.com/paper/2110.02456/) (2021)
- [Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2](https://mlsanity.com/paper/2503.13001/) (2025)
- [Spiky Rank and Its Applications to Rigidity and Circuits](https://mlsanity.com/paper/2602.23503/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)
- [Probabilistic Linear Explanations](https://mlsanity.com/paper/2609.19077/) (2026)

## Abstract (arXiv)

Motivated by the resurgence of neural networks in being able to solve complex learning tasks we undertake a study of high depth networks using ReLU gates which implement the function x mapsto max0,x. We try to understand the role of depth in such neural networks by showing size lowerbounds against such network architectures in parameter regimes hitherto unexplored. In particular we show the following two main results about neural nets computing Boolean functions of input dimension n, 1. We use the method of random restrictions to show almost linear, Omega(ε2(1-δ)n1-δ), lower bound for completely weight unrestricted LTF-of-ReLU circuits to match the Andreev function on at least frac12 +ε fraction of the inputs for ε > √2fraclog^frac 22-δ(n)n for any δ ∈ (0,frac 1 2) 2. We use the method of sign-rank to show exponential in dimension lower bounds for ReLU circuits ending in a LTF gate and of depths upto O(nxi) with xi < frac18 with some restrictions on the weights in the bottom most layer. All other weights in these circuits are kept unrestricted. This in turns also implies the same lowerbounds for LTF circuits with the same architecture and the same weight restrictions on their bottom most layer. Along the way we also show that there exists a ℝ^ nrightarrow ℝ Sum-of-ReLU-of-ReLU function which Sum-of-ReLU neural nets can never represent no matter how large they are allowed to be.