Cover Image

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Antonelli, Melissa, Durand, Arnaud, Li, Rui
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Complexity classification of counting graph homomorphisms modulo a prime number
by: Bulatov, Andrei A., et al.
Published: (2021)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

Efficient derandomization of differentially private counting queries
by: Ghentiyala, Surendra
Published: (2025)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
by: Blanc, Manon, et al.
Published: (2023)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

A proof of P != NP (New symmetric encryption algorithm against any linear attacks and differential attacks)
by: Ming, Gao
Published: (2022)

A model theoretic proof for o-minimal coherence theorem
by: Fu, Yayi
Published: (2023)

Short and useful quantum proofs for sublogarithmic-space verifiers
by: Say, A. C. Cem
Published: (2025)

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Unconditional proofs of quantumness between small-space machines
by: Say, A. C. Cem, et al.
Published: (2024)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
by: Garg, Abhibhav, et al.
Published: (2025)

Constant-depth circuits for polynomial GCD over any characteristic
by: Bhattacharjee, Somnath, et al.
Published: (2025)

On $NP \cap coNP$ proof complexity generators
by: Krajicek, Jan
Published: (2025)

Scheme-theoretic Approach to Computational Complexity I. The Separation of P and NP
by: Çivril, Ali
Published: (2021)

A parametric version of the Hilbert Nullstellensatz
by: Manssour, Rida Ait El, et al.
Published: (2024)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
by: Casteigts, Arnaud, et al.
Published: (2026)

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
by: Casteigts, Arnaud, et al.
Published: (2024)

Lower bounds for set-blocked clauses proofs
by: Yolcu, Emre
Published: (2024)

Experimental relativistic zero-knowledge proofs with unconditional security
by: Weng, Chen-Xun, et al.
Published: (2025)

IQP circuits for 2-Forrelation
by: Buzet, Quentin, et al.
Published: (2026)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

Quantum Merlin-Arthur with an internally separable proof
by: Bassirian, Roozbeh, et al.
Published: (2024)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

An elementary proof that linking problems are hard
by: Cheng, Shannon, et al.
Published: (2025)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Optimising quantum circuits is generally hard
by: van de Wetering, John, et al.
Published: (2023)

Complexity and hardness of random peaked circuits
by: Zhang, Yuxuan
Published: (2025)

Fast simulation of planar Clifford circuits
by: Gosset, David, et al.
Published: (2020)

Incompressibility and spectral gaps of random circuits
by: Chen, Chi-Fang, et al.
Published: (2024)