Algebraic approach to promise constraint satisfaction
From MaRDI portal
Publication:5212802
DOI10.1145/3313276.3316300zbMath1433.68271arXiv1811.00970OpenAlexW3007452340MaRDI QIDQ5212802
Jakub Bulín, Andrei A. Krokhin, Jakub Opršal
Publication date: 30 January 2020
Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.00970
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)
Related Items
Topology and Adjunction in Promise Constraint Satisfaction, The lattice and semigroup structure of multipermutations, Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy, Max-3-Lin over non-abelian groups with universal factor graphs, The algebraic structure of the densification and the sparsification tasks for CSPs, Constraint satisfaction problem: what makes the problem easy, Closed sets of finitary functions between finite fields of coprime order, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, 𝜔-categorical structures avoiding height 1 identities, Revisiting alphabet reduction in Dinur’s PCP., Sandwiches for promise constraint satisfaction, Reflections and powers of multisorted minions, Unnamed Item, Unnamed Item, Unnamed Item, Pseudo‐loop conditions, Smooth digraphs modulo primitive positive constructability and cyclic loop conditions, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, Accessible set functors are universal, Closed sets of finitary functions between products of finite fields of coprime order, Nonfinitely based ai-semirings with finitely based semigroup reducts, Solving CSPs Using Weak Local Consistency
