CS Paper Radar

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

Kuan Cheng, Shengtang Huang, Ruiyang Wu

cs.CC ·submitted 2026-10-19 00:55 UTC · v3

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Random ($\log{n}$)-CNF Formulas Are Hard for Depth-$2$ Frege with Modular Gates

cs.CC ·2026-10-29 ·Jonas Conneryd
theory similarity 0.63
Abstract

We prove that, with high probability, refuting a random $k$-CNF formula on $n$ variables with ${M = n2^{k}}$ clauses for $ω_n(1) \leq k \leq O(\log{n})$ requires polynomial calculus degree at least ${n/2-O(n/\sqrt{k})}$ over every field. Through Pang's recent tradeoff between $\mathsf{AC}^0[p]$-Frege size and polynomial calculus degree [Pang 2026, arXiv:2610.00837v2], this implies a size lower bound of $\exp(Ω_p(\sqrt{k} \log{n}))$ for depth-$2$ $\mathsf{AC}^0[p]$-Frege. In this range of $k$, the bound is superpolynomial in $M$ while $M \leq \mathrm{poly}(n)$. We also prove a nearly matching degree upper bound of $n/2-n\ln(k)/{2k} +O(n/k)$, which shows that other formula families are needed to obtain lower bounds for full $\mathsf{AC}^0[p]$-Frege through Pang's tradeoff.

0.17

Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)

cs.CC ·2026-08-25 ·Youlong Ding, Aayush Jain, Ilan Komargodski
similarity 0.63
Abstract

We obtain new $\mathsf{NC}^1$-computable pseudorandom functions (PRFs) from various standard assumptions, resolving several long-standing open problems. Concretely, for the first time, we obtain $\mathsf{NC}^1$-computable PRFs: (1) from the \textbf{Learning With Errors (LWE)} assumption with a polynomial modulus-to-noise ratio, improving upon prior low-depth constructions that required Ring-LWE with super-polynomial ratios [Banerjee-Peikert-Rosen, EUROCRYPT 2012]; (2) from the \textbf{Learning Parity with Noise (LPN)} assumption, removing the need for structured LPN variants [Boyle et al., FOCS 2020], [Ding-Jain-Komargodski, STOC 2025], [Ding-Jain-Komargodski, TCC 2026]; (3) from the \textbf{Computational Diffie-Hellman (CDH)} assumption; prior works relied on the stronger Decisional Diffie-Hellman (DDH) or generalized Diffie-Hellman (GDH) assumptions [Naor-Reingold, FOCS '97, J. ACM '04]. Technically, our results follow from a new generic transformation that converts weak PRFs computable in depth $d(n) = Ω(\log n)$ to (strong) PRFs computable in depth $O(d(n))$. Roughly speaking, our approach combines \emph{tapering} the internal state of the classical GGM tree (so that the per-leveldepth decreases geometrically) with a two-stage security proof that transitions from a computational to an information-theoretic argument.

0.18

Short Point Lists for CNFs and Stronger Constant-Depth Circuit Hardness

cs.CC math.CO ·2026-10-19 ·Xin Li, Yan Zhong
publishedtheory similarity 0.63
Abstract

We give a short-description decomposition of bounded-width CNFs. For every fixed $\varepsilon>0$, every width-$b$ CNF on $m$ variables is an exact disjoint union of at most $2^{\varepsilon m}$ width-$b$ CNFs, each determined by $2^{O_\varepsilon(b)}\log(m+1)$ satisfying assignments. For every fixed $d\ge3$, we prove a worst-case size lower bound of $2^{Ω_d((n\log n)^{1/(d-1)})}$ against depth-at-most-$d$ unbounded-fan-in AND/OR circuits with input negations for three polynomial-time Boolean families: inverse trace over binary fields, the Goldreich--Tal trilinear function, and OpenAI's polynomial evaluator with its original parameters. All parameter bits count as inputs. For inverse trace, every such circuit of size at most $S$, where $n\le S\le2^{c_dn^{1/(d-1)}}$, has uniform sign correlation at most $2^{-η_dn\log\log S/(\log S)^{d-1}}$. Here $c_d,η_d>0$ depend only on $d$. This improves on the classical parity correlation bound. The lower bounds combine the decomposition with restriction arguments; the correlation bound additionally uses common partial decision trees. We also construct exact nonuniform AND/OR circuits for inverse trace of size $2^{O(n^{2/3})}$ at depth eight and $2^{O(\sqrt n\log n)}$ at depth nine. For every fixed integer $h\ge2$, the construction gives depth-$(4h+1)$ circuits of size $2^{O_h(n^{1/h}\log n)}$. The upper bounds implement finite-field evaluation and interpolation using circuits that enumerate intermediate states.

0.52

A Degree--Size Relation for Resolution over Polynomials

cs.CC cs.LO ·2026-09-30 ·Shuo Pang
similarity 0.61
Abstract · Parameters in Section 8 (Conclusions) made explicit

For every constant-width CNF, we show that linear degree in polynomial calculus (PC) implies exponential size in resolution over constant-degree polynomials, over the same prime field. Applications include exponential lower bounds for CNFs in $\operatorname{Res}(\operatorname{PC}_r/\mathbb{F}_p)$ and hence in $\operatorname{Res}(\oplus_p)$, separations between different moduli, improved lower bounds for $\operatorname{Res}(k)$ up to $k=\varepsilon\log n$, proof-search consequences, and an implication of super-polynomial $AC^0[p]$-Frege bounds from very strong PC degree lower bounds. The proof uses the common-multiplier idea isolated from Braun [arXiv:2609.23015] to construct a Razborov--Smolensky approximation that preserves inferences, without introducing extension variables. The approximation errors are measured by ranks of the multiplication maps induced by the error-witness polynomials, modulo bounded-degree PC consequences.

0.49

Bounds on polynomial approximations of the discrete logarithm function

cs.CC cs.CR ·2026-10-24 ·Swastik Kopparty, Rishabh Kothary, Ashutosh Shankar
publishedtheory similarity 0.61
Abstract

We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the discrete log function. They showed that for any univariate polynomial $f(X) \in \mathbb{F}_p[X]$ with $deg(f) \leq D$, we have: $$ |\{ x \in \mathbb{F}_p^\times \mid f(x) = dlog(x) \}| \leq \sqrt{2 D p}.$$ We show two improvements: (1) For all $D$, we improve the upper bound above to $(1+o(1)) \cdot \sqrt{Dp}$. In particular, we give nontrivial upper bounds on the approximation even for $D > p/2$. This new upper bound is the Johnson bound from the theory of list-decoding of error-correcting codes, and in fact our proof uses a connection to that problem, as well as other combinatorial ideas. (2) For $D = 1$, where both the above bounds are $O(\sqrt{p})$, we give an asymptotically improved upper bound of $O(p^{2/5})$. This is based on the sum-product phenomenon of additive combinatorics. We also improve the [CS00] bounds on the number of points of the form $(x, dlog(x)) \in \mathbb{F}_p^2$ that any bivariate polynomial $Q(X,Y) \in \mathbb{F}_p[X,Y]$ with $deg(Q) \leq D$ can vanish on, with our new bounds approaching the analogue of the Johnson bound for this problem.

0.41

Applicative theories can count

cs.LO ·2026-11-07 ·Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis
hot direction similarity 0.59
Abstract

Applicative theories offer a proof-theoretic framework for studying complexity. In this paper, we introduce a family of applicative theories to characterize classes ranging from constant-depth circuits to polynomial space. Our approach relies on a simple axiom scheme, the small variations of which allows to capture various forms of counting and alternation. This leads to highly uniform results. When applied on notation, the scheme captures bit counting, yielding a characterization of the functions computable by constant-depth, polynomial-size threshold circuits ($\textbf{FTC}^0$); when applied lexicographically, it allows for the counting of accepting computations, yielding a characterization of the functions in the counting hierarchy ($\textbf{FCH}$). Increasing the logical complexity of the induction formulas allowed in the scheme, we obtain characterizations of the functions computable by bounded Boolean circuits of logarithmic-depth and polynomial-size ($\textbf{FNC}^1$) and of the functions computable in polynomial space ($\textbf{FPSPACE}$). The latter characterization solves an open problem in the field. Finally, we investigate separation results. While it is unknown whether $\textbf{FNC}^1$ and $\textbf{FCH}$ are different, there is an oracle relative to which (relativized) $\textbf{FNC}^1$ is strictly contained in (relativized) $\textbf{FCH}$. We use this fact to separate the theories characterizing them, by exploring their ability to represent higher-order functionals.

0.29

Topology inside NC$^1$

cs.CC ·2026-09-10 ·Eric Allender, Samir Datta, Arsenii Karnaukhov, and Grisha Pochuev, Sambuddha Roy +1 more
publishedhighly cited similarity 0.59
Abstract · 9 pages, 4 figures

We show that ACC$^0$ is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC$^0$. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of planarity, including crossing number and thickness. We show that constant-width circuits of polynomial size and thickness two already suffice to capture all of NC$^1$.

0.61

Fooling Thresholds of Halfspaces

cs.CC ·2026-09-18 ·Minglong Qin, Penghui Yao, Mingnan Zhao, Haigang Zhou
theory similarity 0.59
Abstract · 55 pages, including appendices and references

We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $δ$-fools every $k$-out-of-$m$ threshold of $m$ halfspaces over $\{-1,1\}^n$ with seed length $\widetilde{O}(κ^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdotδ^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>0$, where $κ=\min\{k,m-k+1\}$. The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.

0.32