# Shallower ReLU Network Representations via Exact Linear Algebra

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 17 references that are in the map.
- First posted on arXiv 22 Jul 2026.

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

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Maxout Networks](https://mlsanity.com/paper/1302.4389/) (2013)
- [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)
- [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)
- [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)
- [Representing Piecewise Linear Functions by Functions with Small Arity](https://mlsanity.com/paper/2305.16933/) (2023)
- [A Depth Hierarchy for Computing the Maximum in ReLU Networks via Extremal Graph Theory](https://mlsanity.com/paper/2601.01417/) (2026)

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

- [Representing MAX functions using two-hidden-layer ReLU networks](https://mlsanity.com/paper/2608.25221/) (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)

We study the depth required by ReLU networks to exactly represent piecewise linear functions, focusing specifically on the maximum function. This problem has recently received significant attention in both the ML and TCS literature. We prove that maxn(x)=maxx1,ldots,xn is exactly representable with two hidden layers for every n≤ 12. Previously, this was only known up to n≤5 [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26]. We obtain our constructions through an exact computer-assisted search within a space of candidate solutions: After a symmetry reduction, we obtain a finite system of linear equations over mathbbQ such that any solution yields a valid representation of the maximum function. The resulting constructions have a structured first hidden layer, which enables recursive substitution into deeper networks. This yields an exact ReLU representation of maxn with at most lceil log6(n/2) rceil+1 hidden layers. Consequently, every continuous piecewise-linear function on ℝd admits an exact representation with at most lceillog6((d+1)/2)rceil+1 hidden layers; in particular, two hidden layers suffice for d≤ 11. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.