:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Delic, Dejan, Marcoux, John
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Logic in Computer Science 68R
Online Access:	https://arxiv.org/abs/2508.11540
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Singleton algorithms for the Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2025)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

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

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

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

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

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

A note reviewing Turing's 1936
by: Cattabriga, Paola
Published: (2013)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)

Near-Optimal Encodings of Cardinality Constraints
by: Krapivin, Andrew, et al.
Published: (2026)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
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)

On the Complexity of the Skolem Problem at Low Orders
by: Bacik, Piotr, et al.
Published: (2025)

On the Descriptive Complexity of Vertex Deletion Problems
by: Bannach, Max, et al.
Published: (2024)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Toward a Uniform Algorithm and Uniform Reduction for Constraint Problems
by: Barto, Libor, et al.
Published: (2026)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

Quantum Random Self-Modifiable Computation
by: Fiske, Michael Stephen
Published: (2018)

Complexity of Consistency Testing for the Release-Acquire Semantics
by: Govind, R., et al.
Published: (2026)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
by: Ježil, Ondřej, et al.
Published: (2026)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)