← 研踪 PaperTrailarXiv:2610.25623 · v3
High Precision Multiplicative-Error Approximation of $\#$SAC$^1$ Functions in Logspace Uniform AC$^1$
首次提交 2026-10-19 08:55
版本更新 2026-11-06 10:47
雷达观测 2026-11-09 10:16
摘要
We show that approximations of $\#\mathsf{SAC}^1$ functions (i.e. functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits of depth $O(\log n)$) can be computed in logspace uniform $\mathsf{AC}^1$ (denoted as $\mathsf{L}\text{-}\mathsf{AC}^1$) with multiplicative error $2^{-\operatorname{poly}\log n}$.Previously, approximations of $\#\mathsf{SAC}^1$ functions were known to be in logspace-uniform $\mathsf{TC}^1$ via exact computation given by Allender, Jiao, Mahajan, and Vinay (TCS'98). A main corollary of our result is that the following models beyond $\mathsf{BPL}$ are computable by $\mathsf{L}\text{-}\mathsf{AC}^1$ with multiplicative error $2^{-\operatorname{poly}\log n}$: - Probabilistic Auxiliary Push-down Machines (Probabilistic $\mathsf{AuxPDM}$s), which are polynomial time logspace Turing Machines (TMs) with an auxiliary stack having unbounded size and a read-once random tape; - Read-$k$ Probabilistic TMs with polynomial time and logarithmic space, where $k$ is a constant and Read-$k$ means the random tape is two-way accessible and each cell can be visited for at most $k$ times. Notice that this is a direct generalization and improvement for $\mathsf{BPL}\subseteq\mathsf{L}\text{-}\mathsf{AC}^1$ of Cheng and Wang (CCC'24), and the approximation error is improved from additive reverse polynomial to multiplicative reverse quasi-polynomial. $\mathsf{AuxPDM}$ was introduced by Cook (JACM'71) and its probabilistic version was first studied by Macarie and Ogihara (TCS'98). Read-$k$ Probabilistic logspace TMs was studied by Impagliazzo, Nisan, Wigderson (STOC'94) where a pseudorandom generator for this model was given. We mention that multiplicative error approximations are stronger than additive error approximations in the sense that they can even be used to decide non-deterministic computations.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v3 · 2026-11-06 10:47 · 最新观测版本
High Precision Multiplicative-Error Approximation of $\#$SAC$^1$ Functions in Logspace Uniform AC$^1$
We show that approximations of $\#\mathsf{SAC}^1$ functions (i.e. functions computed by logspace-uniform polynomial-size positive semi-unbounded arithmetic circuits of depth $O(\log n)$) can be computed in logspace uniform $\mathsf{AC}^1$ (denoted as $\mathsf{L}\text{-}\mathsf{AC}^1$) with multiplicative error $2^{-\operatorname{poly}\log n}$.Previously, approximations of $\#\mathsf{SAC}^1$ functions were known to be in logspace-uniform $\mathsf{TC}^1$ via exact computation given by Allender, Jiao, Mahajan, and Vinay (TCS'98). A main corollary of our result is that the following models beyond $\mathsf{BPL}$ are computable by $\mathsf{L}\text{-}\mathsf{AC}^1$ with multiplicative error $2^{-\operatorname{poly}\log n}$: - Probabilistic Auxiliary Push-down Machines (Probabilistic $\mathsf{AuxPDM}$s), which are polynomial time logspace Turing Machines (TMs) with an auxiliary stack having unbounded size and a read-once random tape; - Read-$k$ Probabilistic TMs with polynomial time and logarithmic space, where $k$ is a constant and Read-$k$ means the random tape is two-way accessible and each cell can be visited for at most $k$ times. Notice that this is a direct generalization and improvement for $\mathsf{BPL}\subseteq\mathsf{L}\text{-}\mathsf{AC}^1$ of Cheng and Wang (CCC'24), and the approximation error is improved from additive reverse polynomial to multiplicative reverse quasi-polynomial. $\mathsf{AuxPDM}$ was introduced by Cook (JACM'71) and its probabilistic version was first studied by Macarie and Ogihara (TCS'98). Read-$k$ Probabilistic logspace TMs was studied by Impagliazzo, Nisan, Wigderson (STOC'94) where a pseudorandom generator for this model was given. We mention that multiplicative error approximations are stronger than additive error approximations in the sense that they can even be used to decide non-deterministic computations.
查看此版本解读 →查看此版本原文 ↗