On efficiently computable functions, deep networks and sparse compositionality

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]ᵈ→ᵐ is computable in time polynomial in the bit-depths, then for every pair of precisions (n,mₒᵤₜ) there exists a bounded-fan-in Boolean circuit of size and depth (n+mₒᵤₜ) computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth (n+mₒᵤₜ) that achieves accuracy ε=2^-mₒᵤₜ. We also relate these constructions to compositional approximation rates {MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} and to optimization viewed as hierarchical search over sparse structures.