pipette
ENEnglish

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

Kuan Cheng, Shengtang Huang, Ruiyang Wu

Preprint

En palabras de los autores

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.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.