# On efficiently computable functions, deep networks and sparse compositionality

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 11 references that are in the map.
- First posted on arXiv 13 Oct 2025.

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

- [Benefits of depth in neural networks](https://mlsanity.com/paper/1602.04485/) (2016)
- [The Power of Depth for Feedforward Neural Networks](https://mlsanity.com/paper/1512.03965/) (2015)
- [Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review](https://mlsanity.com/paper/1611.00740/) (2016)
- [Auto-Regressive Next-Token Predictors are Universal Learners](https://mlsanity.com/paper/2309.06979/) (2023)

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

- [Learning Sparse Compositional Functions with Norm-Constrained Neural Networks](https://mlsanity.com/paper/2605.25608/) (2026)
- [Generative Interpretability via Scalable Neuro-Symbolic Models](https://mlsanity.com/paper/2609.13529/) (2026)
- [Compositional Sparsity as an Inductive Bias for Neural Architecture Design](https://mlsanity.com/paper/2605.14764/) (2026)

## Abstract (arXiv)

We show that efficient Turing computability at any fixed input/output precision implies the existence of compositionally sparse (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if f:[0,1]d→Rm is computable in time polynomial in the bit-depths, then for every pair of precisions (n,mout) there exists a bounded-fan-in Boolean circuit of size and depth poly(n+mout) computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth poly(n+mout) that achieves accuracy varepsilon=2^-mout. We also relate these constructions to compositional approximation rates citeMhaskarPoggio2016b,poggiodeepshallow2017,Poggio2017,Poggio2023HowDS and to optimization viewed as hierarchical search over sparse structures.