High Precision Multiplicative-Error Approximation of $\mathrm{\#}$SAC${}^1$ Functions in Logspace Uniform AC${}^1$

Cheng and Wang (CCC’ 24) showed that BPL is contained in logspace uniform AC${}^1$ (denoted as L-AC${}^1$). We upgrade their result by showing that $\mathrm{\#}$SAC functions (i.e., functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits) can be approximately computed by L-AC circuits with high precision. In particular, approximations of $\mathrm{\#}$SAC${}^1$ functions can be computed in L-AC${}^1$ with multiplicative error $2^{-\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\log n}$. Previously, approximations of $\mathrm{\#}$SAC${}^1$ functions are known to be in ${\mathsf{N}\mathsf{C}}^2$ via its exact computation given by Vinay (CCC’ 91). A main corollary of our result is that BPAuxPDMs and Read-$k$-BPL are computable by L-AC${}^1$ with multiplicative error $2^{-\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\log n}$. Notice that multiplicative error approximations can be used directly to decide non-deterministic computations. So our L-AC${}^1$ circuits can automatically be used to decide non-deterministic AuxPDMs and hence NL. We note that recently OpenAI announced that BPL $=$ L. Even if we only consider derandomizing BPL, our L-AC${}^1$ computation has the advantage that the error can be $2^{-\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\log n}$ and can be multiplicative.