:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Makowski, Michał
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Information Theory F.1.3; H.1.1
Online Access:	https://arxiv.org/abs/2408.02550
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

A point to set principle for finite-state dimension
by: Mayordomo, Elvira
Published: (2022)

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
by: Bajaj, Divya, et al.
Published: (2026)

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

The Extremum Stack is a Minimal Sufficient Statistic for Rate-Independent Functionals: A Kolmogorov Complexity Characterisation
by: Frydrych, Piotr
Published: (2026)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

Tight bounds on depth-2 QAC-circuits computing parity
by: Fenner, Stephen, et al.
Published: (2025)

Multiplicative Turing Ensembles, Pareto's Law, and Creativity
by: Kolpakov, Alexander, et al.
Published: (2025)

Understanding Robust Catalytic Computing
by: Koucký, Michal, et al.
Published: (2026)

Disjunctive Complexity
by: Ivanov, Nikita, et al.
Published: (2025)

Data accounting and error counting
by: Gajda, Michał J.
Published: (2023)

The Complexity of Strategic Behavior in Primary Elections
by: Cleveland, Colin, et al.
Published: (2026)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)

Anyone but Him: The Complexity of Precluding an Alternative
by: Hemaspaandra, Edith, et al.
Published: (2005)

Stochastic well-structured transition systems
by: Aspnes, James
Published: (2025)

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

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting
by: Hemaspaandra, Lane A., et al.
Published: (2021)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

Average Attention Transformers and Arithmetic Circuits
by: Ehrmuth, Lena, et al.
Published: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Benford's Law from Turing Ensembles and Integer Partitions
by: Kolpakov, Alexander, et al.
Published: (2025)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Realizable Circuit Complexity: Embedding Computation in Space-Time
by: Prada, Benjamin, et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

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

A LOCAL View of the Polynomial Hierarchy
by: Reiter, Fabian
Published: (2023)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

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

Search versus Search for Collapsing Electoral Control Types
by: Carleton, Benjamin, et al.
Published: (2022)

L is different from NP
by: Montoya, J. Andres
Published: (2024)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)