CS Paper Radar

Factor Closure in Noncommutative Algebraic Complexity

V. Arvind, Pushkar S. Joglekar

cs.CC ·submitted 2026-11-01 16:35 UTC · v1
theory

Abstract

We prove that $\VPnc$ is closed under taking factors over every field. If a noncommutative circuit of size $s$ computes a nonconstant polynomial of degree at most $D$, then each left or right factor has a circuit of size $O(sD^3)$. A central factor $g$ in a decomposition $f=agb$, with nonconstant outer factors $a,b$, has a circuit of size $O(sD^6)$. The proof uses a small weighted nondeterministic finite automaton (NFA) with replacement labels. Given $f=gh$, its labels depend on a word of maximum degree in $h$ and the coefficients of its suffixes. A pairing of accepting paths proves that the induced linear map $T$ satisfies $T(gh)=g$. Matrix substitution implements $T$ in a circuit. Applying the same substitution to a Boolean-sum verifier proves $\VNPnc$ closure. The construction also proves formula closure. The automaton has one copying state and, after leaving it, uses only scalar replacements. This structure gives formulas of size $O(s^2)$ for one-sided factors and $O(s^4)$ for central factors of a size-$s$ formula. The same map proves that polynomial-size noncommutative algebraic branching programs are closed under taking factors. Polynomial-size ABP factorizations over finite fields are already known from~\cite{AJ25}. These are arithmetic size bounds, with arbitrary field constants at unit cost, including over $\Q$. Over finite fields, combining the formula construction with~\cite{AJ22} gives randomized polynomial-time complete factorization of formula inputs, with factors output as formulas. For polynomial-degree circuit inputs, we obtain polynomial-length succinct ABP descriptions with polynomial-time edge queries. We also give two algorithms that output complete ordered irreducible factorizations as polynomial-size circuits: a deterministic $\FP^{\SigTwo}$ algorithm and a zero-error randomized algorithm with an NP oracle and expected polynomial running time.

Closest papers

Nearest neighbours by meaning across the whole index.

Deterministic factorization of constant depth circuits from whitebox PIT

cs.CC ·2026-11-06 ·Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi +1 more
similarity 0.60
Abstract

We show that over the field of rational numbers, there is a deterministic algorithm for factorization of constant depth circuits that makes calls to a (whitebox or blackbox) PIT algorithm for such circuits. The time complexity of the algorithm (and hence the number of calls to the PIT oracle) is polynomially bounded in the size and degree of the input circuit. Our reduction to PIT is fairly simple and general and applies as it is to other natural classes of algebraic circuits like formulas and algebraic branching programs. Prior to this work, the known deterministic factorization algorithms for constant depth circuits crucially relied on \emph{blackbox} PIT [Bhattacharjee et al.]. Our main technical ingredient is an efficient, deterministic algorithm that, when given access to sufficiently high degree truncations of \emph{all} the power series roots of a constant depth circuit, uses oracle calls to any (whitebox or blackbox) PIT algorithm for these circuits, and partitions the roots into the sets of conjugates; thereby identifying the irreducible factors. For our proof, we rely on a root recombination criterion using logarithmic derivatives [Sasaki et al., Bostan et al., Lecerf] and show that this criterion can be efficiently and deterministically implemented for power series roots of constant depth circuits using access to any PIT oracle. On the way, we discuss an algorithm that may be of independent interest: it takes as input a matrix whose entries are multivariate constant depth circuits over a field $\mathbb{F}$, requires oracle access to any PIT algorithm for these circuits and outputs a basis for the $\mathbb{F}$-kernel of this matrix in polynomial time.

0.33

Rational Identity Testing for Noncommutative Circuits is in Polynomial Space

cs.CC ·2026-09-29 ·V. Arvind, Pushkar S. Joglekar
publishedtheory similarity 0.58
Abstract

The rational identity testing problem, RIT, asks whether an input \emph{rational circuit}, computes the zero element of the free skew field. For rational \emph{formulas} the problem is known to be in deterministic polynomial time. For rational circuits of size $s$ the associated linear pencil has dimension $2^{O(s)}$, and the known algorithms use exponential time and exponential space. We show that RIT for rational circuits over $Q$ and finite fields is in PSPACE. As a consequence, noncommutative PIT for degree unrestricted noncommutative circuits is also in PSPACE. The proof is based on the following three observations Analyzing the Hrubes-Wigderson construction of a linear pencil for an input rational formula, we obtain a succinctly represented linear pencil $A$ of size $2^{O(s)}$ for the input rational \emph{circuit} of size $s$. More precisely, given indices $i$ and $j$ for the linear pencil we can compute $A_{i,j}$ in space polynomial in $s$ and length of $i,j$. This algorithm essentially gives a succinct presentation of the linear pencil $A$ obtained by the reduction. By the recent theorem of Chatterjee, Ghosh, Gurjar, Raj and Thierauf that deciding whether a symbolic matrix $\sum_i A_ix_i$ has full noncommutative rank is in NC. We note that their algorithm is logspace-uniform NC and we use it as a black-box for computing rank of succinctly represented pencil $A$. Finally, we note a folklore simulation: If a problem is solved by a logspace-uniform family of \emph{deterministic} Boolean circuits of polylogarithmic depth, and its input is not written down but is presented by a polylogspace subroutine that returns any requested input bit, then the circuit can be evaluated in polylogarithmic space. Hence, simulating a depth $O(\log^{i}M)$ circuit for succinctly presented inputs of length $M = 2^{Θ(s)}$ yields a polynomial space algorithm.

0.63

Towards A Parametrized Complexity of Determinization

cs.FL ·2026-11-07 ·Ivan Baburin, Ryan Cotterell
similarity 0.58
Abstract

Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is \textsf{PSPACE}-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, \emph{any} determinization algorithm which runs at least as fast. This result implies that making any \textit{a priori} estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this---in the spirit of parametrized complexity---we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce \emph{subset complexity}---a refinement of the semigroup complexity which has a tighter connection with the subset construction. In certain scenarios, the subset complexity can be approximated in polynomial time, making it potentially viable for more practical applications.

0.25

Depth Hierarchies for Symmetric Algebraic Circuits

cs.CC ·2026-11-17 ·Anuj Dawar, Prateek Dwivedi, Benedikt Pago, Tim Seppelt
similarity 0.58
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.32

Rational Reductions and Regular Languages of Constant Circuit Complexity

cs.CC cs.FLcs.LO ·2026-09-16 ·Stefan Göller, Amaldev Manuel
theory similarity 0.57
Abstract

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

0.26

Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy

cs.CC ·2026-10-30 ·Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
theory similarity 0.57
Abstract · Made some minor changes

Andrews, Garg, and Schost (FOCS~2026) recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time. In fact, we show that the reduction holds both ways, and Integral Closure Membership Testing is equivalent to APS under polynomial-time reductions.

0.17

Hitting sets From Derivations: Waring Rank and Noncommutative ABPs

cs.CC ·2026-09-28 ·Shubham Bhardwaj, Foram Lakhani, Partha Mukhopadhyay, Ramprasad Saptharishi, Pratik Shastri +1 more
similarity 0.56
Abstract

We give an explicit hitting set of size $\operatorname{poly}(n,d,r)$ for the class of $n$-variate degree-$d$ polynomials whose partial derivative space is bounded by $r$, over any field $\mathbb{F}$ of characteristic zero (or large enough). In particular, this yields a polynomial sized hitting set for the class of depth-$3$ powering circuits. The proof extends to the setting of noncommutative ABPs and provides a polynomial sized hitting set (of matrices) for the class of noncommututive polynomials that can be computed by polynomial sized noncommutative ABPs (this was also one of the results reported by Open AI~\cite{OpenAI26} in their release on 6 Oct 2026). The main technical insight is the construction of a ``formal derivation'' and properties of the associated Wronskian with respect to this derivation, which was previously studied by Moura \cite{Moura_2004} in a very different context. The proofs in this paper are elementary and completely self-contained. AI disclosure: A subset of the stewards obtained a weaker statement (hitting sets for polynomials with bounded partial derivative space) during conversations \cite{astra_proof} with OpenAI GPT-6 Astra. Extensions of this idea to the broader class of noncommutative ABPs were obtained by the other stewards (via further conversations with Astra), prior to OpenAI's dump on 6 Oct 2026. The proofs presented in this writeup is a rewriting (in the authors' words) of the proofs for both settings obtained by the models in a form that we believe is understandable to researchers. Although the proof is technically identical to OpenAI's release, we believe this exposition is self-contained, simpler, and more valuable to the community. The absurdity of the situation is not lost on us.

0.56

Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture

cs.CC ·2026-10-13 ·Aaron Sterling
unusual similarity 0.55
Abstract

Liu introduced generalized Fibonacci gates on domains of size 3 and 4, proved that Holant problems built from them are tractable by a cut-and-merge algorithm, and conjectured that Fibonacci gates with matching polynomial-time algorithms exist on all higher domains. We extend the definition uniformly to every domain size $k$ and show that a family of domain-$k$ generalized Fibonacci gates is the same thing as a $k$-dimensional commutative Frobenius (equivalently, Artinian Gorenstein) algebra $A$ equipped with an orthonormal basis containing $1$. Under this dictionary Liu's parameter constraints are exactly associativity of $A$, a gate is an element $w\in A$, merging two gates is multiplication in $A$, and the Holant value of a connected graph $G$ is $τ\bigl(h^{\,|E|-|V|+1}\prod_v w_v\bigr)$ for a fixed ``handle'' element $h\in A$. This proves Liu's conjecture for every $k$, with an algorithm whose cost is polynomial in $k$ as well as in the graph. We also give a closure criterion for linear recurrences of any depth (a balance condition implies closure, and is necessary when the unit is a combination of the colours), and we map the landscape: semisimple algebras are exactly Liu's orthogonal frames, smoothable algebras with nilpotents are collided frames, and families whose algebra is not smoothable (``frameless'' families) exist exactly when $k\ge 14$. Finally we show that every non-semisimple part of a family is invisible to the Holant on connected graphs with two or more independent cycles. This note states the results and sketches the proofs; the proofs of the main theorems are short and are given essentially in full.

0.27