CS Paper Radar

Rational Reductions and Regular Languages of Constant Circuit Complexity

Stefan Göller, Amaldev Manuel

cs.CC cs.FLcs.LO ·submitted 2026-09-16 11:14 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

A Circuit Complexity Trichotomy For Regular Languages

cs.CC cs.FL ·2026-11-02 ·Stefan Göller, Amaldev Manuel
similarity 0.78
Abstract

We establish a trichotomy for the non-uniform, unbounded-fan-in circuit complexity of regular languages: the complexity of every regular language lies in exactly one of $O(1)$, $Ω(\log n)\cap O(\log n\log\log n)$, or $Ω(n)\cap O(n)$. Our main technical contribution is a characterization of the sublinear class in terms of algebra, word congruences, regular expressions, and logic. This class consists precisely of the regular languages computable by constant-depth circuits of size $O(\log^2 n)$, or, equivalently, by circuits of size $O(\log n\log\log n)$ and depth $O((\log\log n)^2)$. Consequently, every regular language of sublinear circuit complexity is definable in $\mathrm{FO}^2[Σ,<,\mathrm{mod}]$, which is contained in wire-linear $\mathbf{AC}^0$. For each of the three classes, deciding membership is $\mathbf{PSPACE}$-complete when the language is specified by a nondeterministic finite automaton. We also obtain a corresponding classification for regular languages with a neutral letter.

0.15

Applicative theories can count

cs.LO ·2026-11-07 ·Melissa Antonelli, Marcel Ertel, Eduardo Skapinakis
hot direction similarity 0.69
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

Depth Hierarchies for Symmetric Algebraic Circuits

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

Descriptive Complexity in Lean: Completeness by First-Order Reductions

cs.LO cs.CC ·2026-09-16 ·Pierre Senellart, Anton Gnatenko
theorycode/data similarity 0.64
Abstract · 25 pages. Library available at https://github.com/PierreSenellart/descriptive-complexity

We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.

0.47

Meta-Mathematics of Algebraic Complexity

cs.CC cs.LO ·2026-10-24 ·Michal Garlik, Svyatoslav Gryaznov, Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
top venue similarity 0.63
Abstract · A preliminary version of this work appeared in the proceedings of ACM-IEEE LICS 2026

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while algebraic circuit lower bounds are hard for somewhat weak proof systems such as Polynomial Calculus Resolution ($\mathsf{PCR}$), contemporary lower bounds are efficiently provable in proof systems and bounded arithmetic theories corresponding to $\mathsf{NC}^2$, such as $\mathsf{VNC}^2$ and the corresponding class of propositional Frege proofs of quasipolynomial-size. Moreover, going below $\mathsf{VNC}^2$ into algebraic constant-depth reasoning is likely insufficient to efficiently prove already constant-depth algebraic circuit lower bounds. Under an algebraic analogue of the Krajicek--Razborov conjecture, our results suggest that proving superpolynomial lower bounds for general algebraic circuits will require stronger reasoning than that used in the rank-based proofs studied here. Specifically, we show the following.

0.49

Independent Languages and Witnesses of Dependence (Non-satisfaction)

cs.FL ·2026-08-25 ·Stavros Konstantinidis
published similarity 0.62
Abstract · In Proceedings AFL 2026, arXiv:2608.23071

We consider the independent language property defined by the language equation φ(X)=\emptyset, where the expression φ involves the language variable X, constant languages, and standard regular operations including transductions, but not complementation. This property consists of all languages L satisfying φ(L)=\emptyset. Depending on the choice of the operations in φ, the equation defines a broad class of codes, including combinations of standard variable-length codes and error-detecting codes. We show that any φ-independence is a Jürgensen independence, we define what a witness of non-satisfaction of φ(X)=\emptyset is, for a language L, and we show how to compute a witness of non-satisfaction when L is regular. We also discuss the complexity of the problem, showing that the decision version of the problem is PSPACE-complete.

0.48

Unary Functions, Automorphisms, and Unlabeled First-Order Model Counting

cs.LO cs.DM ·2026-08-31 ·Ondřej Kuželka
theory similarity 0.62
Abstract · fixed typos, 61 pages

Every fixed first-order sentence $\varphi$ determines an enumerative sequence $n\mapsto \mathrm{FOMC}(\varphi,n)$, counting its models on the labeled domain $[n]$. We study the complexity of these sequences when logical specifications may use genuine unary function symbols and hence nested terms such as $x,f(x),f^2(x),\ldots$. We prove that, for every fixed sentence $\varphi\in \mathrm{C}^1_{=}[f]$ with one unary function and an arbitrary finite relational vocabulary, $\mathrm{FOMC}(\varphi,n)$ is computable in time polynomial in $n$. By contrast, either a second variable or a second unary function yields hardness: there is a fixed sentence in $\mathrm{FO}^2_{=}[f]$ whose model-counting function is $\#\mathrm{P}_1$-complete, and there is a fixed constant-free universal sentence in $\mathrm{FO}^1_{=}[f,g]$, using only unary predicates besides $f$ and $g$, with the same property. We also relate labeled and unlabeled enumeration exactly. For every relational sentence $\varphi$, we construct an extension $\varphi_{\mathrm{aut}}$ in which a unary function records an automorphism and $\mathrm{FOMC}(\varphi_{\mathrm{aut}},n)=n! \cdot \mathrm{UFOMC}(\varphi,n)$, where $\mathrm{UFOMC}(\varphi,n)$ counts the $n$-element models of $\varphi$ up to isomorphism. This gives a one-query exact reduction from unlabeled to labeled model counting at the same domain size. If $\varphi$ belongs to $\mathrm{FO}^k_{=}$, respectively $\mathrm{C}^k$, and its relational vocabulary has maximum arity $r$, eliminating the auxiliary function yields a single-query reduction to labeled model counting in $\mathrm{FO}^{\max\{k,r+1\}}_{=}$, respectively $\mathrm{C}^{\max\{k,r+1\}}$.

0.19

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of Relations

cs.LO cs.CC ·2026-09-22 ·Yuya Uezato, Yoshiki Nakamura
theory similarity 0.62
Abstract · v2: Simplified the construction, streamlined the exposition, and added a subexponential circuit upper bound for fixed vocabularies and expon…

Three-variable first-order logic ($\mathrm{FO}^3$) and the calculus of relations (CoR) define the same binary queries, an equivalence that goes back to Tarski's work in the 1940s. The classical translation from $\mathrm{FO}^3$ to CoR is single-exponential, but it has remained open whether this blowup is necessary. We prove that it is, even over finite structures and even for circuits that share subterms. Our proof introduces a new technique: we modify a single finite structure in exponentially many local ways, each changing the answer of a short $\mathrm{FO}^3$ formula $\varphi$. In any CoR circuit $C$ equivalent to $\varphi$, only compositions of binary relations can notice these modifications, and each composition can notice at most two; thus, $C$ requires exponentially many compositions. The same technique gives an exponential succinctness gap between $\mathrm{FO}^3$ and $\mathrm{FO}^2$, and exponential lower bounds for matrix query languages over the Boolean and tropical semirings, where the analogous question was also open.

0.22