Equivariant algorithms for constraint satisfaction problems over coset templates

DOI10.1016/j.ipl.2016.09.009zbMath1392.68386arXiv1412.4020MaRDI QIDQ344534

Sławomir Lasota

Publication date: 23 November 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.4020

zbMATH Keywords

combinatorial problems; constraint satisfaction problems; bounded width; coset templates; local consistency algorithms

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68Q19: Descriptive complexity and finite models

Cites Work

• Unnamed Item
• Bounded width problems and algebras
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Arities of permutation groups: Wreath products and \(k\)-sets
• The collapse of the bounded width hierarchy
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Constraint Satisfaction Problems of Bounded Width
• Turing Machines with Atoms
• Generalized Majority-Minority Operations are Tractable
• A Simple Algorithm for Mal'tsev Constraints