Semidefinite programming and linear equations vs. homomorphism problems
From MaRDI portal
approximate graph coloringapproximate homomorphism problemlinear Diophantine equationspromise constraint satisfactionsemidefinite programming
Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Applications of universal algebra in computer science (08A70) Linear Diophantine equations (11D04) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computational aspects of satisfiability (68R07) Graph theory (including graph drawing) in computer science (68R10) Semidefinite programming (90C22)
Cites work
- (2+)-Sat is NP-hard
- d-to-1 hardness of coloring 3-colorable graphs with o(1) colors
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A dichotomy theorem for nonuniform CSPs
- A proof of the CSP dichotomy conjecture
- Algebraic Approach to Promise Constraint Satisfaction
- Algorithms in invariant theory
- An algorithmic blend of LPs and ring equations for promise CSPs
- An exact duality theory for semidefinite programming and its complexity implications
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- An invariance principle for the multi-slice, with applications
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximate graph coloring by semidefinite programming
- Approximate Graph Colouring and Crystals
- Approximate graph colouring and the hollow shadow
- Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs
- Approximation algorithms and semidefinite programming.
- Approximation Resistance from Pairwise-Independent Subgroups
- Bipartite Subgraphs and the Smallest Eigenvalue
- CLAP: A New Algorithm for Promise CSPs
- Classification and Analysis of Partially Balanced Incomplete Block Designs with Two Associate Classes
- Classifying the Complexity of Constraints Using Finite Algebras
- Closure properties of constraints
- Cohomology in constraint satisfaction and structure isomorphism
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Computational invariant theory. With two appendices by Vladimir L. Popov and an addendum by Nobert A. Campo and Vladimir L. Popov
- Conditional dichotomy of Boolean ordered promise CSPs
- Conditional Hardness for Approximate Coloring
- CSP gaps and reductions in the lasserre hierarchy
- Current research on algebraic combinatorics. Supplements to our book, Algebraic combinatorics I
- Erdős-Ko-Rado theorems. Algebraic approaches
- Expander flows, geometric embeddings and graph partitioning
- From weak to strong linear programming gaps for all constraint satisfaction problems
- Geometric algorithms and combinatorial optimization.
- Group symmetry in interior-point methods for semidefinite program
- Hierarchies of Minion Tests for PCSPs through Tensors
- How Good is the Goemans--Williamson MAX CUT Algorithm?
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3884178 (Why is no real title available?)
- scientific article; zbMATH DE number 6016068 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 43547 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 635657 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved hardness of approximating chromatic number
- Kneser's conjecture, chromatic number, and homotopy
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Local consistency as a reduction between constraint satisfaction problems
- Lower bounds on the size of semidefinite programming relaxations
- New hardness results for graph and hypergraph colorings
- On Linear Associative Algebras Corresponding to Association Schemes of Partially Balanced Designs
- On the algebraic structure of combinatorial problems
- On the complexity of H-coloring
- 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 Shannon capacity of a graph
- On the Turing model complexity of interior point methods for semidefinite programming
- Promise constraint satisfaction and width
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Proving integrality gaps without knowing the linear program
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Reducibility among combinatorial problems
- Reduction of symmetric semidefinite programs using the regular -representation
- Robustly solvable constraint satisfaction problems
- SDPs and robust satisfiability of promise CSP
- Semidefinite Programming
- Semidefinite programs and association schemes
- Some optimal inapproximability results
- SOS is not obviously automatizable, even approximately
- Sum-of-squares Lower Bounds for Planted Clique
- Symmetry groups, semidefinite programs, and sums of squares
- The Complexity of Near-Optimal Graph Coloring
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The ellipsoid method and its consequences in combinatorial optimization
- The limits of SDP relaxations for general-valued CSPs
- The power of linear programming for general-valued CSPs
- The power of Sherali-Adams relaxations for general-valued CSPs
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- The wonderland of reflections
- Topology and Adjunction in Promise Constraint Satisfaction
- Towards a characterization of constant-factor approximable finite-valued CSPs
- Zur Theorie der Matrices.
- Über Matrizen aus nicht negativen Elementen.
This page was built for publication: Semidefinite programming and linear equations vs. homomorphism problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6975017)
