# Better Neural Network Expressivity: Subdividing the Simplex

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 47 references that are in the map.
- First posted on arXiv 20 May 2025.

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

- [Input Convex Neural Networks](https://mlsanity.com/paper/1609.07152/) (2016)
- [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)
- [Optimal Control Via Neural Networks: A Convex Approach](https://mlsanity.com/paper/1805.11835/) (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)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [More Asymmetry Yields Faster Matrix Multiplication](https://mlsanity.com/paper/2404.16349/) (2024)
- [Improved Bounds on Neural Complexity for Representing Piecewise Linear Functions](https://mlsanity.com/paper/2210.07236/) (2022)
- [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)
- [Input Convex Neural Networks for Building MPC](https://mlsanity.com/paper/2011.13227/) (2020)
- [Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor](https://mlsanity.com/paper/1708.05622/) (2017)
- [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)
- [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)
- [Limits on representing Boolean functions by linear combinations of simple functions: thresholds, ReLUs, and low-degree polynomials](https://mlsanity.com/paper/1802.09121/) (2018)

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

- [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)
- [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)
- [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)
- [A simplex-based measure of symmetry](https://mlsanity.com/paper/2607.03815/) (2026)
- [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)
- [A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers](https://mlsanity.com/paper/2610.04256/) (2026)

## Abstract (arXiv)

This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that lceil log2(n+1) rceil hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on ℝn. Hertrich, Basu, Di Summa, and Skutella (NeurIPS'21 / SIDMA'23) conjectured that this result is optimal in the sense that there are CPWL functions on ℝn, like the maximum function, that require this depth. We disprove the conjecture and show that lceillog3(n-1)rceil+1 hidden layers are sufficient to compute all CPWL functions on ℝn. A key step in the proof is that ReLU neural networks with two hidden layers can exactly represent the maximum function of five inputs. More generally, we show that lceillog3(n-2)rceil+1 hidden layers are sufficient to compute the maximum of n≥ 4 numbers. Our constructions almost match the lceillog3(n)rceil lower bound of Averkov, Hojny, and Merkert (ICLR'25) in the special case of ReLU networks with weights that are decimal fractions. The constructions have a geometric interpretation via polyhedral subdivisions of the simplex into ``easier'' polytopes.