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]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.