Sensitive instances of the constraint satisfaction problem

DOI10.4230/LIPICS.ICALP.2020.110MaRDI QIDQ6842460zbMATH OpenFDO

Authors Libor Barto, Marcin Kozik, Johnson Tan, Matthew Valeriote

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.110

zbMATH Keywords

bounded widthconstraint satisfaction problemlocal consistencyloop lemmanear unanimity operation

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Absorption in universal algebra and CSP
• Characterizations of several Maltsev conditions.
• Congruence distributivity implies bounded width
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraints, consistency and closure
• Datalog and constraint satisfaction with infinite templates
• Finitely related algebras in congruence distributive varieties have near unanimity terms
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• scientific article; zbMATH DE number 3424072 (Why is no real title available?)
• On the existence of subalgebras of direct products with prescribed d-fold projections
• Polynomial interpolation and the Chinese remainder theorem for algebraic systems
• Problems and results in tame congruence theory. A survey of the '88 Budapest workshop
• Testing assignments to constraint satisfaction problems
• The collapse of the bounded width hierarchy
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The weakest nontrivial idempotent equations

This page was built for publication: Sensitive instances of the constraint satisfaction problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842460)