Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub Algebraic approach to promise constraint satisfaction. (English) Zbl 1433.68271 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 602-613 (2019). Cited in 11 Documents MSC: 68R07 Computational aspects of satisfiability 05C15 Coloring of graphs and hypergraphs 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68Q25 Analysis of algorithms and problem complexity Keywords:approximation; constraint satisfaction; graph colouring; polymorphism; promise problem PDF BibTeX XML Cite \textit{J. Bulín} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 602--613 (2019; Zbl 1433.68271) Full Text: DOI arXiv OpenURL