Topology and Adjunction in Promise Constraint Satisfaction
From MaRDI portal
(Redirected from Topology and Adjunction in Promise Constraint Satisfaction)
Recommendations
- Algebraic Approach to Promise Constraint Satisfaction
- Algebraic approach to promise constraint satisfaction
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Algebraic theory of promise constraint satisfaction problems, first steps
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
Cites work
- (2+)-Sat is NP-hard
- \(\mathbb{Z}_2\)-indices and Hedetniemi's conjecture
- A Characterisation of First-Order Constraint Satisfaction Problems
- A proof of the CSP dichotomy conjecture
- A survey on Hedetniemi's conjecture
- Algebraic approach to promise constraint satisfaction
- Algebraic Approach to Promise Constraint Satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- Applications of product colouring
- Arc colorings of digraphs
- Box complexes and homotopy theory of graphs
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Closure properties of constraints
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Combinatorial algebraic topology
- Complexes of graph homomorphisms
- Conditional Hardness for Approximate Coloring
- Counterexamples to Hedetniemi's conjecture
- Dichotomy for symmetric Boolean PCSPs
- Digraph functors which admit both left and right adjoints
- Dismantlability, connectedness, and mixing in relational structures
- Drei Sätze über die n-dimensionale euklidische Sphäre
- Galois theory for minors of finite functions
- Hedetniemi's conjecture and adjoint functors in thin categories
- Hedetniemi's conjecture and strongly multiplicative graphs
- Homomorphism reconfiguration via homotopy
- scientific article; zbMATH DE number 37867 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 7359806 (Why is no real title available?)
- Improved hardness for \(H\)-colourings of \(G\)-colourable graphs
- Improved hardness of approximating chromatic number
- Improved Inapproximability of Rainbow Coloring
- Kneser's conjecture, chromatic number, and homotopy
- Loop conditions for strongly connected digraphs
- New hardness results for graph and hypergraph colorings
- NP-hardness of coloring 2-colorable hypergraph with poly-logarithmically many colors
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- On the arc-chromatic number of a digraph
- On the complexity of H-coloring
- On the conditional hardness of coloring a 4-colorable graph with super-constant number of colors
- On the Hardness of 4-Coloring a 3-Colorable Graph
- On the hardness of approximating the chromatic number
- On the power of unique 2-prover 1-round games
- On the Simple ℤ2-homotopy Types of Graph Complexes and Their Simple ℤ2-universality
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Rainbow coloring hardness via low sensitivity polymorphisms
- Robustly solvable constraint satisfaction problems
- Square-free graphs are multiplicative
- Strong inapproximability results on balanced rainbow-colorable hypergraphs
- Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
- The Complexity of Near-Optimal Graph Coloring
- The complexity of promise SAT on non-Boolean domains
- 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 PCP theorem by gap amplification
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- The Quest for Strong Inapproximability Results with Perfect Completeness
- The wonderland of reflections
- Topological lower bounds for the chromatic number: a hierarchy
- Towards a proof of the 2-to-1 games conjecture?
- Undirected connectivity in log-space
- Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
- WI-posets, graph complexes and \(\mathbb{Z}_2\)-equivalences
Cited in
(23)- Topology and adjunction in promise constraint satisfaction
- Approximate graph colouring and the hollow shadow
- Functors on relational structures which admit both left and right adjoints
- Geometric, algebraic and topological combinatorics. Abstracts from the workshop held December 10--15, 2023
- Promise and infinite-domain constraint satisfaction
- Quantum advantage and CSP complexity
- Solving promise equations over monoids and groups
- A topological version of Schaefer's dichotomy theorem
- Right-adjoints for Datalog programs
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- Approximate graph coloring and the crystal with a hollow shadow
- 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
- Semidefinite programming and linear equations vs. homomorphism problems
- 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
- Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
- New hardness results for low-rank matrix completion
- Restricted CSPs and \(\mathbb{F}\)-free digraph algorithmics
- Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
This page was built for publication: Topology and Adjunction in Promise Constraint Satisfaction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5885596)
