Buchumschlag

On the Complexity of the Conditional Independence Implication Problem With Bounded Cardinalities

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Makowski, Michał
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Information Theory F.1.3; H.1.1
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Counting Complexity of the Skolem Problem
von: Jindal, Gorav, et al.
Veröffentlicht: (2024)

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)

Explicit Commutative ROABPs from Partial Derivatives
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

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

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

Tight bounds on depth-2 QAC-circuits computing parity
von: Fenner, Stephen, et al.
Veröffentlicht: (2025)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
von: Esparza, Javier, et al.
Veröffentlicht: (2025)

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

Understanding Robust Catalytic Computing
von: Koucký, Michal, 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)

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

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

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

Multiplicative Turing Ensembles, Pareto's Law, and Creativity
von: Kolpakov, Alexander, et al.
Veröffentlicht: (2025)

The Complexity of Strategic Behavior in Primary Elections
von: Cleveland, Colin, et al.
Veröffentlicht: (2026)

Stochastic well-structured transition systems
von: Aspnes, James
Veröffentlicht: (2025)

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

Data accounting and error counting
von: Gajda, Michał J.
Veröffentlicht: (2023)

On Sampling Lower Bounds for Polynomials
von: Khodabandeh, Mohammad Mahdi, et al.
Veröffentlicht: (2026)

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

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)

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

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

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

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

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

Anyone but Him: The Complexity of Precluding an Alternative
von: Hemaspaandra, Edith, et al.
Veröffentlicht: (2005)

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

On the Complexity of Problems on Graphs Defined on Groups
von: Das, Bireswar, et al.
Veröffentlicht: (2025)

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

Benford's Law from Turing Ensembles and Integer Partitions
von: Kolpakov, Alexander, et al.
Veröffentlicht: (2025)

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

$\rm P$ has polynomial-time finite-state verifiers
von: Gezer, M. Utkan, et al.
Veröffentlicht: (2023)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

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

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