Buchumschlag

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Antonelli, Melissa, Durand, Arnaud, Kontinen, Juha
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity F.1.3; F.2.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

On bounded depth proofs for Tseitin formulas on the grid; revisited
von: Håstad, Johan, et al.
Veröffentlicht: (2022)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2019)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
von: Kawałek, Piotr, et al.
Veröffentlicht: (2026)

Quantum Sabotage Complexity
von: Cornelissen, Arjan, et al.
Veröffentlicht: (2024)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
von: Hemaspaandra, Lane A., et al.
Veröffentlicht: (2021)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

Graph-Based Deterministic Polynomial Framwork for NP Problems
von: Lee, Changryeol
Veröffentlicht: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
von: Idziak, Paweł M., et al.
Veröffentlicht: (2025)

Direct Sums for Parity Decision Trees
von: Besselman, Tyler, et al.
Veröffentlicht: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Symmetric Arithmetic Circuits
von: Dawar, Anuj, et al.
Veröffentlicht: (2020)

Imperative process algebra and models of computation
von: Middelburg, C. A.
Veröffentlicht: (2022)

Algorithmic hardness of the partition function for nucleic acid strands
von: Ducloz, Gwendal, et al.
Veröffentlicht: (2025)

Lower Bounds for Symmetric Circuits for the Determinant
von: Dawar, Anuj, et al.
Veröffentlicht: (2021)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
von: Anand, Emile, et al.
Veröffentlicht: (2024)

Realizable Circuit Complexity: Embedding Computation in Space-Time
von: Prada, Benjamin, et al.
Veröffentlicht: (2025)

Arithmetic Complexity of Solutions of the Dirichlet Problem
von: Boche, Holger, et al.
Veröffentlicht: (2026)

Catalytic Computing and Register Programs Beyond Log-Depth
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

A point to set principle for finite-state dimension
von: Mayordomo, Elvira
Veröffentlicht: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
von: Bajaj, Divya, et al.
Veröffentlicht: (2026)

L is different from NP
von: Montoya, J. Andres
Veröffentlicht: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
von: Behera, Amik Raj, et al.
Veröffentlicht: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
von: Kühn, Kolja, et al.
Veröffentlicht: (2026)

Disjunctive Complexity
von: Ivanov, Nikita, et al.
Veröffentlicht: (2025)

Hausdorff Reductions and the Exponential Hierarchies
von: Malizia, Enrico
Veröffentlicht: (2024)

Understanding Robust Catalytic Computing
von: Koucký, Michal, et al.
Veröffentlicht: (2026)

On the Satisfaction Probabilities of $k$-CNF Formulas
von: Tantau, Till
Veröffentlicht: (2022)

Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
von: Saha, Barna, et al.
Veröffentlicht: (2024)

Certificate-Sensitive Subset Sum: Realizing Instance Complexity
von: Salas, Jesus
Veröffentlicht: (2025)

Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2024)

Average Attention Transformers and Arithmetic Circuits
von: Ehrmuth, Lena, et al.
Veröffentlicht: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
von: Barlag, Timon, et al.
Veröffentlicht: (2026)