Shallower ReLU Network Representations via Exact Linear Algebra

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.