# Representing MAX functions using two-hidden-layer ReLU networks

arXiv: https://arxiv.org/abs/2608.25221 · HTML: https://mlsanity.com/paper/2608.25221/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 7 references that are in the map.
- First posted on arXiv 25 Aug 2026.

## Builds on (most cited first, 6 of 6)

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Lower Bounds on the Depth of Integral ReLU Neural Networks via Lattice Polytopes](https://mlsanity.com/paper/2302.12553/) (2023)
- [On the Expressiveness of Rational ReLU Neural Networks With Bounded Depth](https://mlsanity.com/paper/2502.06283/) (2025)
- [Better Neural Network Expressivity: Subdividing the Simplex](https://mlsanity.com/paper/2505.14338/) (2025)
- [Depth-Bounds for Neural Networks via the Braid Arrangement](https://mlsanity.com/paper/2502.09324/) (2025)
- [Shallower ReLU Network Representations via Exact Linear Algebra](https://mlsanity.com/paper/2607.21651/) (2026)

## Built on by (most cited first, 1 of 1)

- [A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers](https://mlsanity.com/paper/2610.04256/) (2026)

## Abstract (arXiv)

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.