×

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).

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
PDF BibTeX XML Cite
Full Text: DOI arXiv