# On the algorithmic construction of deep ReLU networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 24 references that are in the map.
- First posted on arXiv 23 Jun 2025.

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

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Optimal approximation of piecewise smooth functions using deep ReLU neural networks](https://mlsanity.com/paper/1709.05289/) (2017)
- [Representation Benefits of Deep Feedforward Networks](https://mlsanity.com/paper/1509.08101/) (2015)
- [Rational neural networks](https://mlsanity.com/paper/2004.01902/) (2020)
- [Neural networks and rational functions](https://mlsanity.com/paper/1706.03301/) (2017)
- [Expressivity of Deep Neural Networks](https://mlsanity.com/paper/2007.04759/) (2020)
- [Differentiable Sorting Networks for Scalable Sorting and Ranking Supervision](https://mlsanity.com/paper/2105.04019/) (2021)
- [Exponential ReLU Neural Network Approximation Rates for Point and Edge Singularities](https://mlsanity.com/paper/2010.12217/) (2020)
- [Neural Network Approximation of Refinable Functions](https://mlsanity.com/paper/2107.13191/) (2021)
- [Function approximation by deep networks](https://mlsanity.com/paper/1905.12882/) (2019)
- [Approximation Power of Deep Neural Networks: an explanatory mathematical survey](https://mlsanity.com/paper/2207.09511/) (2022)
- [Learning on manifolds without manifold learning](https://mlsanity.com/paper/2402.12687/) (2024)
- [Exponential Expressivity of ReLUk Neural Networks on Gevrey Classes with Point Singularities](https://mlsanity.com/paper/2403.02035/) (2024)

## Abstract (arXiv)

It is difficult to describe in mathematical terms what a neural network trained on data represents. On the other hand, there is a growing mathematical understanding of what neural networks are in principle capable of representing. Feedforward neural networks using the ReLU activation function represent continuous and piecewise linear functions and can approximate many others. The study of their expressivity addresses the question: which ones? Contributing to the available answers, we take the perspective of a neural network as an algorithm. In this analogy, a neural network is programmed constructively, rather than trained from data. An interesting example is a sorting algorithm: we explicitly construct a neural network that sorts its inputs exactly, not approximately, and that, in a sense, has optimal computational complexity if the input dimension is large. Such constructed networks may have several billion parameters. We construct and analyze several other examples, both existing and new. We find that, in these examples, neural networks as algorithms are typically recursive and parallel. Compared to conventional algorithms, ReLU networks are restricted by having to be continuous. Moreover, the depth of recursion is limited by the depth of the network, with deep networks having superior properties over shallow ones.