Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

DOI10.1016/J.IC.2022.104954MaRDI QIDQ2105441zbMATH OpenOpenAlexFDO

Authors Alex Brandts, S. Zivny

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2022.104954

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Dichotomy for symmetric Boolean PCSPs
• Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• The complexity of promise SAT on non-Boolean domains

Cites work

• (2+)-Sat is NP-hard
• A proof of the CSP dichotomy conjecture
• 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
• Closure properties of constraints
• Conditional Hardness for Approximate Coloring
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
• Improved Inapproximability of Rainbow Coloring
• On the complexity of H-coloring
• On the power of unique 2-prover 1-round games
• Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
• Reducibility among combinatorial problems
• The Complexity of Near-Optimal Graph Coloring
• The complexity of promise SAT on non-Boolean domains
• The complexity of satisfiability problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The hardness of 3-uniform hypergraph coloring
• The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
• The wonderland of reflections

Cited in

(7)

• Dichotomy for symmetric Boolean PCSPs
• CLAP: A New Algorithm for Promise CSPs
• Solving promise equations over monoids and groups
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• 1-in-3 vs. not-all-equal: dichotomy of a broken promise
• On the complexity of symmetric vs. functional PCSPs
• Solving promise equations over monoids and groups

This page was built for publication: Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2105441)