Notes on CSPs and Polymorphisms

2022/10/13 by Zarathustra Brady, Brady, Zarathustra · 3 citations
Computer Science · #Constraint Satisfaction and Optimization

paper · pdf · doi:10.48550/arxiv.2210.07383

Abstract

These are notes from a multi-year learning seminar on the algebraic approach to Constraint Satisfaction Problems (CSPs). The main topics covered are the theory of algebraic structures with few subpowers, the theory of absorbing subalgebras and its applications to studying CSP templates which can be solved by local consistency methods, and the dichotomy theorem for conservative CSP templates. Subsections and appendices cover supplementary material.

Cited by

• Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
• Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
• Mal'cev clones over a three-element set up to minor-equivalence

Related

• Proof complexity of CSP
• A Proof of the CSP Dichotomy Conjecture
• On the induced problem for fixed-template CSPs
• Asking the metaquestions in constraint tractability
• A categorical perspective on constraint satisfaction: The wonderland of adjunctions