# A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 32 references that are in the map.
- First posted on arXiv 4 Jan 2026.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (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)
- [Complexity of Linear Regions in Deep Networks](https://mlsanity.com/paper/1901.09021/) (2019)
- [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)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [On the Approximation Power of Two-Layer Networks of Random ReLUs](https://mlsanity.com/paper/2102.02336/) (2021)
- [Depth Separations in Neural Networks: What is Actually Being Separated?](https://mlsanity.com/paper/1904.06984/) (2019)
- [Lower bounds over Boolean inputs for deep neural networks with ReLU gates](https://mlsanity.com/paper/1711.03073/) (2017)
- [The Connection Between Approximation, Depth Separation and Learnability in Neural Networks](https://mlsanity.com/paper/2102.00434/) (2021)
- [Depth separation beyond radial functions](https://mlsanity.com/paper/2102.01621/) (2021)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Optimization-Based Separations for Neural Networks](https://mlsanity.com/paper/2112.02393/) (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)
- [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)
- [The Theoretical Expressiveness of Maxpooling](https://mlsanity.com/paper/2203.01016/) (2022)
- [Depth Separations in Neural Networks: Separating the Dimension from the Accuracy](https://mlsanity.com/paper/2402.07248/) (2024)

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

- [Most ReLU Networks Admit Identifiable Parameters](https://mlsanity.com/paper/2605.03601/) (2026)
- [Shallower ReLU Network Representations via Exact Linear Algebra](https://mlsanity.com/paper/2607.21651/) (2026)
- [Every Layer Counts: An Exponential L2 Depth Hierarchy for ReLU Networks](https://mlsanity.com/paper/2608.23877/) (2026)

## Abstract (arXiv)

We consider the problem of exact computation of the maximum function over d real inputs using ReLU neural networks. We prove a depth hierarchy, wherein width Omegabig(d^1+frac12k-2-1big) is necessary to represent the maximum for any depth 3≤ k≤ log2(log2(d)). This is the first unconditional super-linear lower bound for this fundamental operator at depths k≥3, and it holds even if the depth scales with d. Our proof technique is based on a combinatorial argument and associates the non-differentiable ridges of the maximum with cliques in a graph induced by the first hidden layer of the computing network, utilizing Tur'an's theorem from extremal graph theory to show that a sufficiently narrow network cannot capture the non-linearities of the maximum. This suggests that despite its simple nature, the maximum function possesses an inherent complexity that stems from the geometric structure of its non-differentiable hyperplanes, and provides a novel approach for proving lower bounds for deep neural networks.