Approximate graph colouring and the hollow shadow
From MaRDI portal
Publication:6499253
Cites work
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 2117181 (Why is no real title available?)
- scientific article; zbMATH DE number 7724184 (Why is no real title available?)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A proof of the CSP dichotomy conjecture
- Absorption in universal algebra and CSP
- Algebraic Approach to Promise Constraint Satisfaction
- An algorithmic blend of LPs and ring equations for promise CSPs
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Approximation Resistance from Pairwise-Independent Subgroups
- Arc colorings of digraphs
- CLAP: A New Algorithm for Promise CSPs
- CSP gaps and reductions in the lasserre hierarchy
- Class of global minimum bounds of polynomial functions
- Coloring 3-colorable graphs with less than \(n^{1/5}\) colors
- Conditional Hardness for Approximate Coloring
- Constrained \((0,1)\)-matrix completion with a staircase of fixed zeros
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constructing \((0,1)\)-matrices with given line sums and certain fixed zeros
- Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem
- From weak to strong linear programming gaps for all constraint satisfaction problems
- Improved hardness of approximating chromatic number
- Improving the performance guarantee for approximate graph coloring
- Inapproximability of combinatorial problems via small LPs and SDPs
- Integral matrices with given row and column sums
- Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
- Lower bounds on the size of semidefinite programming relaxations
- Matrices of zeros and ones with given line sums and a zero block
- New hardness results for graph and hypergraph colorings
- On independent sets, 2-to-2 games, and Grassmann graphs
- On non-optimally expanding sets in Grassmann graphs
- 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
- Optimal inapproximability of satisfiable k-LIN over non-abelian groups
- Patterns that allow given row and column sums
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Properties of a Class of (0,1)-Matrices Covering a given Matrix
- Proving integrality gaps without knowing the linear program
- Pseudorandom sets in Grassmann graph have near-perfect expansion
- Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
- Reducibility among combinatorial problems
- 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 collapse of the bounded width hierarchy
- The complexity of promise SAT on non-Boolean domains
- The complexity of satisfiability problems
- The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
- Topology and Adjunction in Promise Constraint Satisfaction
- Towards a proof of the 2-to-1 games conjecture?
- Transportation matrices with staircase patterns and majorization
- Zero-one matrices with zero trace
- \((2+\varepsilon)\)-Sat is NP-hard
This page was built for publication: Approximate graph colouring and the hollow shadow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499253)
