CS Paper Radar

New Gate, Weight and Wire Complexity Bounds for Sigmoid Neural Networks

Jiatu Li, Daniel Reichman, Ryan Williams, Tony Wu

cs.CC ·submitted 2026-11-16 21:25 UTC · v1
theory

Abstract

Feedforward neural networks with sigmoid activations are of fundamental importance in neural computation. However, our understanding of the circuit complexity of such networks for implementing Boolean functions remains limited. The analog output of the sigmoid, along with its transcendental nature, leads to unique mathematical challenges for proving lower bounds. Introducing new techniques, we establish new upper and lower bounds on the complexity of sigmoidal networks computing Boolean functions: We prove nearly tight bounds for the wire complexity of computing PARITY with such networks of constant depth and polynomial-bounded weights. We extend the size lower bound of Kane and Williams [STOC'16] against depth-$3$ threshold circuits, to depth-3 sigmoidal networks with polynomial weights, proving a $Ω(n^{1.5}/(\log n)^{O(1)})$ size lower bound for computing an explicit function in $\mathsf{P}$. We prove that every symmetric function on $n$ bits can be computed by a depth-$3$ sigmoidal network with $O(n)$ wires and polynomial weights. This stands in stark contrast with threshold circuits of $d=O(1)$ depth, where $n^{1+α_d}$-wire lower bounds are known for $α_d > 0$. We also answer a few fundamental problems related to sigmoidal networks, including proving new simulations and separations between threshold circuits and sigmoidal networks. We establish these results using a variety of techniques, including random restrictions for sigmoid gates, analyzing the average sensitivity of networks with sigmoids, simulation arguments, and using tools from approximation theory, complex analysis, and algebraic geometry.

Closest papers

Nearest neighbours by meaning across the whole index.

Depth Hierarchies for Symmetric Algebraic Circuits

cs.CC ·2026-11-17 ·Anuj Dawar, Prateek Dwivedi, Benedikt Pago, Tim Seppelt
similarity 0.67
Abstract · submitted to STOC 2027

Algebraic complexity studies the cost of computing families of polynomials by algebraic circuits, with the central goal of proving super-polynomial circuit lower bounds and separations between different models of algebraic computation. Since such lower bounds remain elusive for general circuits, a common strategy is to focus on restricted models. A recent line of work (ICALP 2020, ITCS & STOC 2026) introduces and studies symmetry as a syntactic circuit restriction, showing exponential symmetric lower bounds for the permanent, as well as separations between symmetric analogues of algebraic formulas ($\mathsf{VF}$), skew circuits ($\mathsf{VS}$), and circuits ($\mathsf{VP}$). We investigate the role of depth as a complexity parameter in symmetric circuits. For every fixed $Δ\geq 1$, we exhibit a family of polynomials computable by symmetric circuits of polynomial size and depth $2Δ+3$, but requiring size $n^{Ω(\log n)}$ at depth $Δ$. We also define symmetric versions of the bounded-depth algebraic complexity classes $\mathsf{VAC}^k$, for all $k \in \mathbb{N}$, that we call $\mathsf{symVAC}^k$, and establish two strict hierarchies: Firstly, a hierarchy within $\mathsf{symVAC}^0$, and secondly, a hierarchy of the form $\mathsf{symVAC}^k \subsetneq \mathsf{symVAC}^{k+1}$ for all $k$. The latter shows that symmetric circuits of depth $(\log n)^{k+1}$ are strictly more powerful than depth-$(\log n)^k$ circuits. Moreover, we place the bounded-depth classes within the landscape of symmetric algebraic complexity developed by Dwivedi, Pago and Seppelt (STOC 2026). We complement this picture by introducing $\mathsf{symVNP}$, a symmetric analogue of $\mathsf{VNP}$, and establishing $\mathsf{symVNP}$-completeness of the permanent under symmetric projections.

0.29

The Head Complexity of Boolean Functions in Single-Layer Attention

cs.CC cs.LG ·2026-09-03 ·Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye
theory similarity 0.64
Abstract · 32 pages, 0 figures

What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure: $k$ heads compute $k$-bit parity but cannot compute $(k+1)$-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting decision polynomial omits at least one of the $k+1$ input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions: $2^n$ heads suffice to compute every $n$-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require $Ω(2^n/n^2)$ heads. This lower bound matches the upper bound to within a $\operatorname{poly}(n)$ factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.

0.39

Learning Depth-3 Circuits with Polynomial Savings

cs.DS cs.CC ·2026-09-16 ·Xi Chen, Animesh Fatehpuria, Shyamal Patel, Rocco Servedio
similarity 0.64
Abstract

We study the challenging problem of learning depth-three circuits in the mistake-bound model of (realizable) online learning, which is a more difficult model than distribution-free PAC learning. Prior algorithms for this problem, due to Servedio and Tan [ST17], could only learn polynomial-size depth-three circuits of poly$(n)$ size over $\{0,1\}^n$ with a running time of $2^{n - Ω(n/\log n)}$, and hence they ran in time $N^{1-o(1)}$ where $N=2^n$ is the running time of a naive memorization-based approach. In this work we substantially improve on the [ST17] result: for any constant $γ\geq1$, we give an algorithm that learns depth-three circuits of size $n^γ$ with running time \[ 2^{n-c_γn}, \] where $c_γ>0$ depends only on $γ$ and not on $n$. Hence we achieve a polynomial savings over the naive approach for learning any polynomial-size depth-three circuit. The main driving force behind our improvement is an improved bound on the approximate degree of width-$k$ CNFs. Inspired by Szegedy [Sze04] and Magniez et al. [MNRS11], the rough idea of our construction is to use a Chebyshev polynomial to efficiently amplify the spectral gap of a carefully designed random walk. This is combined with a random-restriction-like approach to separately learn different subfunctions corresponding to different assignments to a randomly chosen set of variables, using the Perceptron algorithm over a specially designed feature space. A simplified warmup instantiation of our approach achieves $c_γ= \exp(-O(γ))$; by augmenting this warmup with further ingredients we obtain the sharp form of our result, which achieves $c_γ=Ω(1)/γ$.

0.20

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

Optimal Shallow Circuits for Majority

cs.CC ·2026-09-27 ·Victor Lecomte, Prasanna Ramakrishnan
theoryhighly cited similarity 0.63
Abstract

Four decades on, Håstad's classical $2^{Ω(n^{1/(d-1)})}$ lower bound for depth-$d$ circuits computing Parity remains the best known $\mathrm{AC}^0$ circuit lower bound for any explicit function. Majority has long been a compelling candidate for stronger lower bounds: the most natural circuits computing it are substantially larger than those for Parity and have repeatedly been conjectured to be optimal. We present a simple construction, found by GPT-6 Astra, of depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$ for any symmetric function. This result settles the asymptotic $\mathrm{AC}^0$ circuit complexity of Majority, matching Håstad's lower bound. The proof draws inspiration from well-loved combinatorial tools, including the color-coding technique of Alon, Yuster, and Zwick (1995).

0.33

Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks

cs.LG math.ACmath.AG ·2026-08-27 ·Kathlén Kohn, Giovanni Luca Marchetti, Alex Massarenti, Massimiliano Mella
theoryhighly cited similarity 0.63
Abstract

Motivated by theoretical problems in deep learning, we conjecture that post-composing a fixed number of pairwise distinct nonconstant polynomials with a generic polynomial of sufficiently large degree yields linearly independent polynomials. This generalizes Newman--Slater's theorem on powers of polynomials. We establish several cases of this conjecture and its origin-passing variant: We prove the result for two polynomials, and for an arbitrary number of polynomials when their degrees are bounded. Furthermore, we show how the conjecture implies a complete understanding of the identifiability (i.e., parameter symmetries) of deep fully connected neural network architectures with generic polynomial activation functions. In particular, for network architectures with layer-specific activations of increasing degree, our established versions of the conjecture fully characterize the set of parameters yielding the same end-to-end network function. As a special case, we fully resolve the identifiability of shallow polynomial networks.

0.43

A Top-Down Depth-Four Circuit Lower Bound for Majority

cs.CC ·2026-08-10 ·Hao Wu, Yaqiao Li
theory similarity 0.61
Abstract

We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.

0.32

Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

cs.LG cs.LO ·2026-10-12 ·Daumantas Kojelis, Carsten Lutz
theory similarity 0.61
Abstract

A landmark result states that the expressive power of graph neural networks (GNNs) is bounded from above by the 1-dimensional Weisfeiler-Leman (1-WL) test. We ask whether a constant-depth GNN can match the expressive power of 1-WL while using only rational weights. We prove that this is the case when Schanuel's conjecture, a famous open problem from transcendental number theory, is taken to be true. Our GNN construction works even with integer weights, and more generally with a broad range of rational weights. As the activation function, it may use logistic sigmoid, hyperbolic tangent, or related functions. It is uniform across all graph sizes. We also prove a partial converse: if a GNN with exponentiation, hyperbolic sine or hyperbolic cosine as activation matches the expressive power of the 1-WL test in a slightly more expressive setting where graphs may contain certain auxiliary vertices, then this implies Schanuel's conjecture restricted to the numbers that arise in computations of the GNN. We also conduct experiments showing that the constructed GNNs indeed match the 1-WL test.

0.22