Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 1: Folded Symmetric PCSPs Avoiding Parity, Majority and Alternating-Threshold Have Only C-Fixing PolymorphismsResearch Paper
A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…