{"ID":2856590,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.11942","arxiv_id":"2510.11942","title":"On efficiently computable functions, deep networks and sparse compositionality","abstract":"We show that \\emph{efficient Turing computability} at any fixed input/output precision implies the existence of \\emph{compositionally sparse} (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if $f:[0,1]^d\\to\\R^m$ is computable in time polynomial in the bit-depths, then for every pair of precisions $(n,m_{\\mathrm{out}})$ there exists a bounded-fan-in Boolean circuit of size and depth $\\poly(n+m_{\\mathrm{out}})$ computing the discretized map; replacing each gate by a constant-size neural emulator yields a deep network of size/depth $\\poly(n+m_{\\mathrm{out}})$ that achieves accuracy $\\varepsilon=2^{-m_{\\mathrm{out}}}$. We also relate these constructions to compositional approximation rates \\cite{MhaskarPoggio2016b,poggio_deep_shallow_2017,Poggio2017,Poggio2023HowDS} and to optimization viewed as hierarchical search over sparse structures.","short_abstract":"We show that \\emph{efficient Turing computability} at any fixed input/output precision implies the existence of \\emph{compositionally sparse} (bounded-fan-in, polynomial-size) DAG representations and of corresponding neural approximants achieving the target precision. Concretely: if $f:[0,1]^d\\to\\R^m$ is computable in...","url_abs":"https://arxiv.org/abs/2510.11942","url_pdf":"https://arxiv.org/pdf/2510.11942v1","authors":"[\"Tomaso Poggio\"]","published":"2025-10-13T21:05:18Z","proceeding":"cs.LG","tasks":"[\"cs.LG\"]","methods":"[]","has_code":false}