# Representing Piecewise Linear Functions by Functions with Small Arity

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 16 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [Towards Lower Bounds on the Depth of ReLU Neural Networks](https://mlsanity.com/paper/2105.14835/) (2021)
- [Sharp bounds for the number of regions of maxout networks and vertices of Minkowski sums](https://mlsanity.com/paper/2104.08135/) (2021)
- [Novel convex decomposition of piecewise affine functions](https://mlsanity.com/paper/2108.03950/) (2021)

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

- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Shallower ReLU Network Representations via Exact Linear Algebra](https://mlsanity.com/paper/2607.21651/) (2026)
- [Representing Piecewise-Linear Functions by Functions with Minimal Arity](https://mlsanity.com/paper/2406.02421/) (2024)
- [The Topos of Transformer Networks](https://mlsanity.com/paper/2403.18415/) (2024)
- [Linear-Size Neural Network Representation of Piecewise Affine Functions in ℝ2](https://mlsanity.com/paper/2503.13001/) (2025)
- [On the expressivity of sparse maxout networks](https://mlsanity.com/paper/2510.14068/) (2025)
- [Hidden Monotonicity: Explaining Deep Neural Networks via their DC Decomposition](https://mlsanity.com/paper/2601.07700/) (2026)

## Abstract (arXiv)

A piecewise linear function can be described in different forms: as an arbitrarily nested expression of min- and max-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function there exists a linear combination of max-functions with at most n+1 arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we prove that the piecewise linear function max(0, x1, ldots, xn) cannot be represented as a linear combination of maxima of less than n+1 affine-linear arguments. This was conjectured by Wang and Sun in 2005 in a paper on representations of piecewise linear functions as linear combination of maxima.