High precision approximation of counting functions in logspace uniform circuits
High Precision Multiplicative-Error Approximation of $\#$SAC$^1$ Functions in Logspace Uniform AC$^1$
Computational Complexity
Summary
This paper improves how certain complex counting problems can be approximated using very efficient circuits that run with limited memory. The authors show that specific functions, called #SAC1 functions, can be approximated with extremely small multiplicative errors by circuits in a class called logspace uniform AC1. This advances previous work that placed such approximations in a slightly larger class called NC2. Their results also imply more efficient ways to decide problems related to nondeterministic computations with precise error control.
What this means in practice
- •For complexity theorists: Use improved small-memory circuit models to analyze complexity classes with high-precision approximations.
- •For algorithm designers: Develop algorithms that approximate counting problems with guaranteed exponential precision using efficient, uniform circuits.
A theory result. No direct application yet.
Authors
Kuan Cheng, Shengtang Huang, Ruiyang Wu
Abstract
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 $\#$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 $\#$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 BPAuxPDMs and Read-$k$-BPL are computable by L-AC$^1$ with multiplicative error $2^{-\mathrm{poly}\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{poly}\log n}$ and can be multiplicative.