Algebraic Approach to Promise Constraint Satisfaction
From MaRDI portal
Recommendations
- Algebraic approach to promise constraint satisfaction
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- An algorithmic blend of LPs and ring equations for promise CSPs
Cited in
(54)- The complexity of promise SAT on non-Boolean domains
- Approximating the orthogonality dimension of graphs and hypergraphs
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- The generic circular triangle-free graph
- Quantum advantage and CSP complexity
- Local consistency as a reduction between constraint satisfaction problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Algebraic approach to approximation
- Injective hardness condition for PCSPs
- Conditional dichotomy of Boolean ordered promise CSPs
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- On the descriptive complexity of temporal constraint satisfaction problems
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- Sandwiches for promise constraint satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Functors on relational structures which admit both left and right adjoints
- Clonoids between modules
- Linearly ordered colourings of hypergraphs
- Solving promise equations over monoids and groups
- On the complexity of symmetric vs. functional PCSPs
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- The Sherali-Adams and Weisfeiler-Leman hierarchies in (promise valued) constraint satisfaction problems
- GMSNP and finite structures
- Clonoids of Boolean functions with a linear source clone and a semilattice or 0- or 1-separating target clone
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Majority-closed minions of Boolean functions
- Clonoids of Boolean functions with a monotone or discriminator source clone
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- The complexity of promise constraint satisfaction problem seen from the other side
- Beyond PCSP (1-in-3, NAE)
- Clonoids of Boolean functions with essentially unary, linear, semilattice, or 0- or 1-separating source and target clones
- Robust Factorizations and Colorings of Tensor Graphs
- Promise and infinite-domain constraint satisfaction
- Aggregation of evaluations without unanimity
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Quantum advantage and CSP complexity
- Submaximal clones over a three-element set up to minor-equivalence
- Multisorted Boolean clones determined by binary relations up to minion homomorphisms
- Small Promise CSPs that reduce to large CSPs
- Solving promise equations over monoids and groups
- A logarithmic approximation of linearly-ordered colourings
- Flexible constraint satisfiability and a problem in semigroup theory
- Near-unanimity-closed minions of Boolean functions
- Algebraic approach to promise constraint satisfaction
- Approximate graph colouring and the hollow shadow
- SDPs and robust satisfiability of promise CSP
- Undefinability of approximation of 2-to-2 games
- Improved linearly ordered colorings of hypergraphs via SDP rounding
- Approximate graph coloring and the crystal with a hollow shadow
- Semidefinite programming and linear equations vs. homomorphism problems
This page was built for publication: Algebraic Approach to Promise Constraint Satisfaction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056418)
