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

Overview & Synopsis

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 approximations of $\#$SAC$^1$ functions can be computed in L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Previously, approximations of $\#$SAC$^1$ functions are known to be in $\mathsf{NC}^2$ via its exact computation given by Vinay (CCC' 91). A main corollary of our result is that Probabilisitic polynomial time logspace AuxPDMs and Read-$k$ logspace PTMs are computable by L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\log n}$. Notice that multiplicative error approximations are stronger than additive error approximations in the sense that they can be used to decide both non-deterministic computations and two-sided error probabilistic computations. We note that recently OpenAI announced that BPL $=$ L. Even if we only consider derandomizing probabilistic logspace, our L-AC$^1$ computation has the advantage that the error can be $2^{-\mathrm{poly}\log n}$ and can be multiplicative.