Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

DOI10.1137/19M128212XzbMath1494.68094arXiv1704.01937OpenAlexW3212768336MaRDI QIDQ5096441

Joshua Brakensiek, Venkatesan Guruswami

Publication date: 17 August 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingpolymorphismPCP theoremconstraint satisfactionpromise problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Approximation algorithms (68W25) Computational aspects of satisfiability (68R07)

Related Items (3)

CLAP: A New Algorithm for Promise CSPs ⋮ Topology and Adjunction in Promise Constraint Satisfaction ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finitely related clones and algebras with cube terms.
• Gap theorems for robust satisfiability: Boolean CSPs and beyond
• Conservative constraint satisfaction re-revisited
• Existence theorems for weakly symmetric operations
• On the complexity of H-coloring
• On the algebraic structure of combinatorial problems
• Galois theory for minors of finite functions
• The hardness of 3-uniform hypergraph coloring
• Improved Hardness of Approximating Chromatic Number
• Complexity of conservative constraint satisfaction problems
• The Complexity of Finite-Valued CSPs
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• A finer reduction of constraint problems to digraphs
• Non-dichotomies in Constraint Satisfaction Complexity
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On the Hardness of 4-Coloring a 3-Colorable Graph
• A Proof of the CSP Dichotomy Conjecture
• The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
• Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
• Improved hardness for H-colourings of G-colourable graphs
• Constraint Satisfaction Problems of Bounded Width
• Algebraic approach to promise constraint satisfaction
• An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
• Classifying the Complexity of Constraints Using Finite Algebras
• $(2+\varepsilon)$-Sat Is NP-hard
• New hardness results for graph and hypergraph colorings
• The complexity of satisfiability problems
• A Simple Algorithm for Mal'tsev Constraints
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• On the hardness of approximating the chromatic number

This page was built for publication: Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy