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

DOI10.1016/j.ic.2022.104954OpenAlexW4294630911MaRDI QIDQ2105441

Stanislav Živný, Alex Brandts

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)

Related Items (1)

CLAP: A New Algorithm for Promise CSPs

Cites Work

• Unnamed Item
• On the complexity of H-coloring
• The wonderland of reflections
• The hardness of 3-uniform hypergraph coloring
• Conditional Hardness for Approximate Coloring
• On the power of unique 2-prover 1-round games
• The Complexity of Near-Optimal Graph Coloring
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• Reducibility among Combinatorial Problems
• Algebraic Approach to Promise Constraint Satisfaction
• The Complexity of Promise SAT on Non-Boolean Domains
• Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
• A Proof of the CSP Dichotomy Conjecture
• The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
• Improved hardness for H-colourings of G-colourable graphs
• Improved Inapproximability of Rainbow Coloring
• 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
• The complexity of satisfiability problems

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