Cover Image

The Complexity of Resilience Problems via Valued Constraint Satisfaction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodirsky, Manuel, Semanišinová, Žaneta, Lutz, Carsten
Format:	Preprint
Published:	2023
Subjects:	Logic Computational Complexity Databases 68Q25, 08A70, 68P15 F.4.1; F.2.2; H.2.0
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
by: Bodirsky, Manuel, et al.
Published: (2024)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

Complexity Classification Transfer for CSPs via Algebraic Products
by: Bodirsky, Manuel, et al.
Published: (2022)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Polynomial definability in constraint languages with few subpowers
by: Bulín, Jakub, et al.
Published: (2023)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

Approximate Integrity Constraints in Incomplete Databases With Limited Domains
by: Al-atar, Munqath, et al.
Published: (2024)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Quantum Advantage in Computational Chemistry?
by: Gundlach, Hans, et al.
Published: (2025)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

Approximate Keys and Functional Dependencies in Incomplete Databases With Limited Domains-Algorithmic Perspective
by: Al-atar, Munqath, et al.
Published: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
by: Wulf, Lasse
Published: (2025)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

AVEC: Bootstrapping Privacy for Local LLMs
by: Gaikwad, Madhava
Published: (2025)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)

How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

ABox Abduction for Inconsistent Knowledge Bases under Repair Semantics
by: Haak, Anselm, et al.
Published: (2026)

Polynomial-time Tractable Problems over the $p$-adic Numbers
by: Fehm, Arno, et al.
Published: (2025)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)

Overcoming Over-Fitting in Constraint Acquisition via Query-Driven Interactive Refinement
by: Balafas, Vasileios, et al.
Published: (2025)

Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
by: Golovach, Petr A., et al.
Published: (2022)

TreeWidzard: An Engine for Width-Based Dynamic Programming and Automated Theorem Proving
by: Oliveria, Mateus de Oliveira, et al.
Published: (2026)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)