:: Library Catalog

Image de couverture de livre

Enregistré dans:

Détails bibliographiques
Auteur principal:	Mayordomo, Elvira
Format:	Preprint
Publié:	2022
Sujets:	Computational Complexity F.1.3; F.1.1
Accès en ligne:	https://arxiv.org/abs/2208.00157
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Catalytic Computing and Register Programs Beyond Log-Depth
par: Alekseev, Yaroslav, et autres
Publié: (2025)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
par: Bajaj, Divya, et autres
Publié: (2026)

Imperative process algebra and models of computation
par: Middelburg, C. A.
Publié: (2022)

On the Counting Complexity of the Skolem Problem
par: Jindal, Gorav, et autres
Publié: (2024)

Explicit Commutative ROABPs from Partial Derivatives
par: Bhargava, Vishwas, et autres
Publié: (2024)

$\rm P$ has polynomial-time finite-state verifiers
par: Gezer, M. Utkan, et autres
Publié: (2023)

Tight bounds on depth-2 QAC-circuits computing parity
par: Fenner, Stephen, et autres
Publié: (2025)

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities
par: Makowski, Michał
Publié: (2024)

Stochastic well-structured transition systems
par: Aspnes, James
Publié: (2025)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
par: Esparza, Javier, et autres
Publié: (2025)

Graph Neural Networks and Arithmetic Circuits
par: Barlag, Timon, et autres
Publié: (2024)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
par: Dörfler, Julian, et autres
Publié: (2024)

Average Attention Transformers and Arithmetic Circuits
par: Ehrmuth, Lena, et autres
Publié: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
par: Barlag, Timon, et autres
Publié: (2026)

Nonuniform Deterministic Finite Automata over finite algebraic structures
par: Idziak, Paweł M., et autres
Publié: (2025)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
par: Antonelli, Melissa, et autres
Publié: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
par: Kawałek, Piotr, et autres
Publié: (2026)

L is different from NP
par: Montoya, J. Andres
Publié: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
par: Behera, Amik Raj, et autres
Publié: (2026)

Completing the Complexity Classification of 2-Solo Chess: Knights and Kings are Hard
par: Kühn, Kolja, et autres
Publié: (2026)

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
par: Hemaspaandra, Lane A., et autres
Publié: (2021)

Disjunctive Complexity
par: Ivanov, Nikita, et autres
Publié: (2025)

Hausdorff Reductions and the Exponential Hierarchies
par: Malizia, Enrico
Publié: (2024)

Understanding Robust Catalytic Computing
par: Koucký, Michal, et autres
Publié: (2026)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
par: Anand, Emile, et autres
Publié: (2024)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
par: Schewe, Klaus-Dieter
Publié: (2020)

Algorithmic hardness of the partition function for nucleic acid strands
par: Ducloz, Gwendal, et autres
Publié: (2025)

Realizable Circuit Complexity: Embedding Computation in Space-Time
par: Prada, Benjamin, et autres
Publié: (2025)

A LOCAL View of the Polynomial Hierarchy
par: Reiter, Fabian
Publié: (2023)

On the Complexity of Determinations
par: Hellerstein, Joseph M.
Publié: (2026)

Graph-Based Deterministic Polynomial Framwork for NP Problems
par: Lee, Changryeol
Publié: (2025)

Structure of sparse Boolean functions over Abelian groups, and its application to testing
par: Chakraborty, Sourav, et autres
Publié: (2024)

On bounded depth proofs for Tseitin formulas on the grid; revisited
par: Håstad, Johan, et autres
Publié: (2022)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
par: Conneryd, Jonas, et autres
Publié: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
par: de Rezende, Susanna F., et autres
Publié: (2026)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
par: de Rezende, Susanna F., et autres
Publié: (2024)

Supercritical Tradeoffs for Monotone Circuits
par: Göös, Mika, et autres
Publié: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
par: Tantau, Till
Publié: (2022)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
par: Conneryd, Jonas, et autres
Publié: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
par: Kelley, Zander, et autres
Publié: (2023)