Shallower ReLU Network Representations via Exact Linear Algebra
TL;DR
It is proved that $\max_n(x)$ is exactly representable with two hidden layers for every $n\leq 12$, and these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.
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 $\max_n(x)=\max\{x_1,\ldots,x_n\}$ is exactly representable with two hidden layers for every $n\leq 12$. Previously, this was only known up to $n\leq5$ [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 $\mathbb{Q}$ 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 $\lceil \log_6(n/2) \rceil+1$ hidden layers. Consequently, every continuous piecewise-linear function on $\mathbb{R}^d$ admits an exact representation with at most $\lceil\log_6((d+1)/2)\rceil+1$ hidden layers; in particular, two hidden layers suffice for $d\leq 11$. Again, these results improve upon [Bakaev, Brunck, Hertrich, Stade, Yehudayoff, STOC'26], who proved analogous logarithmic bounds with base three.