scientific article; zbMATH DE number 7561550

DOI10.4230/LIPIcs.ICALP.2019.57MaRDI QIDQ5091214

Marcin Kozik, Szymon Stankiewicz, Miroslav Olšák, Miron Ficak

Publication date: 21 July 2022

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algebraic approachpromise constraint satisfaction problemPCSP

Mathematics Subject Classification ID

Theory of computing (68Qxx) Theory of software (68Nxx)

Related Items

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Improved Hardness of Approximating Chromatic Number
• Conditional hardness for approximate coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Algebraic approach to promise constraint satisfaction
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• The Complexity of General-Valued CSPs
• New hardness results for graph and hypergraph colorings
• The complexity of satisfiability problems
• Robust satisfiability of constraint satisfaction problems

This page was built for publication: