Representing MAX functions using two-hidden-layer ReLU networks

We study exact representations of MAXN(x)=maxx1,ldots,xN using two-hidden-layer ReLU neural networks. This problem has been studied in recent years in an attempt to characterize the exact number of hidden layers required to represent continuous piecewise linear functions. The best lower bound is 2, while the current upper bound is logarithmic in N. It remains completely open if the right answer is a constant number of hidden layers (possibly even 2!) or not. In fact, a recent breakthrough was the representation of MAX5 as a two-hidden-layer ReLU function obtained in [Bakaev et al., 2026], and the case of MAXN was stated as open for N≥ 6 in that paper. Using a careful computer assisted search, we obtain two-hidden-layer ReLU representations of MAX5, MAX6, MAX7, and MAX8. We obtain these by considering rational linear combinations of terms of the form maxsumr=1smax(xar,xbr),sumr=1smax(xcr,xdr), where ar,br,cr,dr∈1,ldots,N. Each inner maximum of two coordinates can be computed in a first hidden layer, and the outer maximum of the two side-sums can be computed in a second hidden layer. Consequently, every finite linear combination of these terms has a two-hidden-layer ReLU realization. An identity for MAXN in this form therefore gives an exact two-hidden-layer ReLU representation of MAXN. Very recently, two-hidden-layer representations of MAXN of the above form were obtained for all N≤ 10 in [Ruess et al., 2026]. Our representations are different and were developed independently. While our techniques share most of the high-level ideas presented in [Ruess et al., 2026], there are also some minor differences which may be of interest for future research on this problem.