# Depth-Bounds for Neural Networks via the Braid Arrangement

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 45 references that are in the map.
- First posted on arXiv 13 Feb 2025.

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

- [Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks](https://mlsanity.com/paper/1702.01135/) (2017)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [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)
- [Tropical Geometry of Deep Neural Networks](https://mlsanity.com/paper/1805.07091/) (2018)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Tight Hardness Results for Training Depth-2 ReLU Networks](https://mlsanity.com/paper/2011.13550/) (2020)
- [Analyzing Deep Neural Networks with Symbolic Propagation: Towards Higher Precision and Faster Verification](https://mlsanity.com/paper/1902.09866/) (2019)
- [The Real Tropical Geometry of Neural Networks](https://mlsanity.com/paper/2403.11871/) (2024)
- [Training Neural Networks is NP-Hard in Fixed Dimension](https://mlsanity.com/paper/2303.17045/) (2023)
- [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)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Provably Good Solutions to the Knapsack Problem via Neural Networks of Bounded Size](https://mlsanity.com/paper/2005.14105/) (2020)
- [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)
- [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)
- [On Minimal Depth in Neural Networks](https://mlsanity.com/paper/2402.15315/) (2024)
- [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)

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

- [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)
- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [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)
- [Arithmetic Circuits and Neural Networks for Regular Matroids](https://mlsanity.com/paper/2511.02406/) (2025)
- [Representing MAX functions using two-hidden-layer ReLU networks](https://mlsanity.com/paper/2608.25221/) (2026)
- [Maxout Polytopes](https://mlsanity.com/paper/2509.21286/) (2025)
- [On the expressivity of sparse maxout networks](https://mlsanity.com/paper/2510.14068/) (2025)
- [Tropical Circuits with Scalar Multiplication Gates](https://mlsanity.com/paper/2607.11540/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## Abstract (arXiv)

We contribute towards resolving the open question of how many hidden layers are required in ReLU networks for exactly representing all continuous and piecewise linear functions on ℝd. While the question has been resolved in special cases, the best known lower bound in general is still 2. We focus on neural networks that are compatible with certain polyhedral complexes, more precisely with the braid fan. For such neural networks, we prove a non-constant lower bound of Omega(loglog d) hidden layers required to exactly represent the maximum of d numbers. Additionally, under our assumption, we provide a combinatorial proof that 3 hidden layers are necessary to compute the maximum of 5 numbers; this had only been verified with an excessive computation so far. Finally, we show that a natural generalization of the best known upper bound to maxout networks is not tight, by demonstrating that a rank-3 maxout layer followed by a rank-2 maxout layer is sufficient to represent the maximum of 7 numbers.