Shallower ReLU Network Representations via Exact Linear Algebra
Abstract
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)=max{x1,…,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 ℚ 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 ⌈ log6(n/2) ⌉+1 hidden layers. Consequently, every continuous piecewise-linear function on ℝd admits an exact representation with at most ⌈log6((d+1)/2)⌉+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.
Related
- The Buchholz Algebra from the Universal Resolvent Algebra--Particle Structure, Gibbs States, and Closed-Path Expansions without Fock Representations
- The Extension groups of one K-type representations of graded Hecke algebra
- Continuous representations of the meta Hahn algebra and special functions
- Representations of the infinite Cuntz algebra
- Middle convolution for Lie algebra representations
BibTeX
@misc{rueß2026shallower,
title = {{Shallower ReLU Network Representations via Exact Linear Algebra}},
author = {Kilian Rueß and Gennadiy Averkov and Florestan Brunck and Moritz Grillo and Christoph Hertrich and Georg Loho and Jack Stade and Moritz Stargalla and Matthew Sun and Martin Winter},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.21651},
eprint = {2607.21651},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.21651},
}
RIS
TY - UNPB
TI - Shallower ReLU Network Representations via Exact Linear Algebra
AU - Kilian Rueß
AU - Gennadiy Averkov
AU - Florestan Brunck
AU - Moritz Grillo
AU - Christoph Hertrich
AU - Georg Loho
AU - Jack Stade
AU - Moritz Stargalla
AU - Matthew Sun
AU - Martin Winter
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2607.21651
UR - https://arxiv.org/abs/2607.21651
AB - 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 max_n(x)=max{x_1,…,x_n} 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 ℚ 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 max_n with at most ⌈ log_6(n/2) ⌉+1 hidden layers. Consequently, every continuous piecewise-linear function on ℝ^d admits an exact representation with at most ⌈log_6((d+1)/2)⌉+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.
ER -