# Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 35 references that are in the map.
- First posted on arXiv 24 Feb 2023.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [On the Expressive Power of Deep Neural Networks](https://mlsanity.com/paper/1606.05336/) (2016)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Approximating Continuous Functions by ReLU Nets of Minimal Width](https://mlsanity.com/paper/1710.11278/) (2017)
- [Universal Function Approximation by Deep Neural Nets with Bounded Width and ReLU Activations](https://mlsanity.com/paper/1708.02691/) (2017)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Why Deep Neural Networks for Function Approximation?](https://mlsanity.com/paper/1610.04161/) (2016)
- [Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networks](https://mlsanity.com/paper/1610.09887/) (2016)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Depth Separation for Neural Networks](https://mlsanity.com/paper/1702.08489/) (2017)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [A Tropical Approach to Neural Networks with Piecewise Linear Activations](https://mlsanity.com/paper/1805.08749/) (2018)
- [The Computational Complexity of ReLU Network Training Parameterized by Data Dimensionality](https://mlsanity.com/paper/2105.08675/) (2021)
- [Lower bounds over Boolean inputs for deep neural networks with ReLU gates](https://mlsanity.com/paper/1711.03073/) (2017)
- [Neural Networks Should Be Wide Enough to Learn Disconnected Decision Regions](https://mlsanity.com/paper/1803.00094/) (2018)
- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [Neural networks with linear threshold activations: structure and algorithms](https://mlsanity.com/paper/2111.08117/) (2021)

## Built on by (most cited first, 30 of 36)

- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [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)
- [On the Depth of Monotone ReLU Neural Networks and ICNNs](https://mlsanity.com/paper/2505.06169/) (2025)
- [Topological Expressivity of ReLU Neural Networks](https://mlsanity.com/paper/2310.11130/) (2023)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Neural Networks and (Virtual) Extended Formulations](https://mlsanity.com/paper/2411.03006/) (2024)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Constraining the outputs of ReLU neural networks](https://mlsanity.com/paper/2508.03867/) (2025)
- [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)
- [Defining Neural Network Architecture through Polytope Structures of Dataset](https://mlsanity.com/paper/2402.02407/) (2024)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)
- [Toric geometry of ReLU neural networks](https://mlsanity.com/paper/2509.05894/) (2025)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [New Complexity-Theoretic Frontiers of Tractability for Neural Network Training](https://mlsanity.com/paper/2607.20811/) (2026)
- [Neural Polytopes](https://mlsanity.com/paper/2307.00721/) (2023)
- [Extracting Formulae in Many-Valued Logic from Deep Neural Networks](https://mlsanity.com/paper/2401.12113/) (2024)
- [Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2](https://mlsanity.com/paper/2503.13001/) (2025)
- [Training-Time Batch Normalization Reshapes Local Partition Geometry in Piecewise-Affine Networks](https://mlsanity.com/paper/2605.04946/) (2026)
- [AffineLens: Capturing the Continuous Piecewise Affine Functions of Neural Networks](https://mlsanity.com/paper/2605.06218/) (2026)
- [Region Seeding via Pre-Activation Regularization: A Geometric View of Piecewise Affine Neural Networks](https://mlsanity.com/paper/2605.06300/) (2026)
- [Representing MAX functions using two-hidden-layer ReLU networks](https://mlsanity.com/paper/2608.25221/) (2026)
- [Computability of Classification and Deep Learning: From Theoretical Limits to Practical Feasibility through Quantization](https://mlsanity.com/paper/2408.06212/) (2024)
- [Optimization over Trained (and Sparse) Neural Networks: A Surrogate within a Surrogate](https://mlsanity.com/paper/2505.01985/) (2025)
- [Approximation Depth of Convex Polytopes](https://mlsanity.com/paper/2507.07779/) (2025)
- [Maxout Polytopes](https://mlsanity.com/paper/2509.21286/) (2025)

## Abstract (arXiv)

We prove that the set of functions representable by ReLU neural networks with integer weights strictly increases with the network depth while allowing arbitrary width. More precisely, we show that lceillog2(n)rceil hidden layers are indeed necessary to compute the maximum of n numbers, matching known upper bounds. Our results are based on the known duality between neural networks and Newton polytopes via tropical geometry. The integrality assumption implies that these Newton polytopes are lattice polytopes. Then, our depth lower bounds follow from a parity argument on the normalized volume of faces of such polytopes.