Shallower ReLU Network Representations via Exact Linear Algebra

We study the number of hidden layers required by ReLU networks to represent piecewise-linear functions exactly, focusing 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,\dots ,x_n\}$ is exactly representable with two hidden layers for every $n\le 12$. Previously, the largest known arity was $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 $\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 networks with more hidden layers. 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\le 11$. These results improve upon Bakaev, Brunck, Hertrich, Stade, and Yehudayoff [STOC '26], who proved analogous logarithmic bounds with base three.