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
(63)- Sandwiches for promise constraint satisfaction
- Beyond PCSP (\textbf{1-in-3}, \textbf{NAE})
- Algebraic theory of promise constraint satisfaction problems, first steps
- Promise constraint satisfaction: structure theory and a symmetric Boolean dichotomy
- Small Promise CSPs that reduce to large CSPs
- The complexity of promise SAT on non-Boolean domains
- 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
- Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
- Algebraic approach to promise constraint satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- Approximating the orthogonality dimension of graphs and hypergraphs
- CLAP: A New Algorithm for Promise CSPs
- Topology and Adjunction in Promise Constraint Satisfaction
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- Majority-closed minions of Boolean functions
- Robust Factorizations and Colorings of Tensor Graphs
- Submaximal clones over a three-element set up to minor-equivalence
- SDPs and robust satisfiability of promise CSP
- Approximate graph colouring and the hollow shadow
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- Conditional dichotomy of Boolean ordered promise CSPs
- On the descriptive complexity of temporal constraint satisfaction problems
- Functors on relational structures which admit both left and right adjoints
- Clonoids between modules
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Multisorted Boolean clones determined by binary relations up to minion homomorphisms
- Near-unanimity-closed minions of Boolean functions
- The complexity of promise constraint satisfaction problem seen from the other side
- Promise and infinite-domain constraint satisfaction
- Quantum advantage and CSP complexity
- Clonoids of Boolean functions with a monotone or discriminator source clone
- Solving promise equations over monoids and groups
- Clonoids of Boolean functions with essentially unary, linear, semilattice, or 0- or 1-separating source and target clones
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- A logarithmic approximation of linearly-ordered colourings
- Approximate graph coloring and the crystal with a hollow shadow
- Flexible constraint satisfiability and a problem in semigroup theory
- The generic circular triangle-free graph
- Local consistency as a reduction between constraint satisfaction problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Quantum advantage and CSP complexity
- Algebraic approach to approximation
- Injective hardness condition for PCSPs
- Semidefinite programming and linear equations vs. homomorphism problems
- 1-in-3 vs. not-all-equal: dichotomy of a broken promise
- Linearly ordered colourings of hypergraphs
- On the complexity of symmetric vs. functional PCSPs
- Solving promise equations over monoids and groups
- 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
- Beyond PCSP (1-in-3, NAE)
- Aggregation of evaluations without unanimity
- Undefinability of approximation of 2-to-2 games
- Improved linearly ordered colorings of hypergraphs via SDP rounding
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Constraint satisfaction problems, compactness and non-measurable sets
- New hardness results for low-rank matrix completion
- Three fundamental questions in modern infinite-domain constraint satisfaction
- Equations over finite monoids with infinite promises
- Optimal inapproximability of promise equations over finite groups
- Maximum and- vs. even-SAT
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)
