Algebraic Approach to Promise Constraint Satisfaction

DOI10.1145/3457606zbMath1499.68140OpenAlexW2898776142MaRDI QIDQ5056418

Libor Barto, Jakub Opršal, Andrei A. Krokhin, Jakub Bulín

Publication date: 8 December 2022

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3457606

zbMATH Keywords

approximationpolymorphismgraph colouringconstraint satisfactionpromise problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Small Promise CSPs that reduce to large CSPs ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Unnamed Item ⋮ Majority-closed minions of Boolean functions ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Submaximal clones over a three-element set up to minor-equivalence ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

This page was built for publication: Algebraic Approach to Promise Constraint Satisfaction