pipette
ESEspañol

High Precision Multiplicative-Error Approximation of SAC Functions in Logspace Uniform AC

Kuan Cheng, Shengtang Huang, Ruiyang Wu

Preprint

In the authors' words

Cheng and Wang (CCC' 24) showed that BPL is contained in logspace uniform AC (denoted as L-AC). 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 functions can be computed in L-AC with multiplicative error . Previously, approximations of SAC functions are known to be in via its exact computation given by Vinay (CCC' 91). A main corollary of our result is that BPAuxPDMs and Read--BPL are computable by L-AC with multiplicative error . Notice that multiplicative error approximations can be used directly to decide non-deterministic computations. So our L-AC 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 computation has the advantage that the error can be and can be multiplicative.

Main resultLimitation the authors admit

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.