Approximate graph colouring and the hollow shadow

DOI10.1145/3564246.3585112WikidataQ130994122 ScholiaQ130994122MaRDI QIDQ6499253FDOQ6499253

Publication date: 8 May 2024

Diophantine equations promise constraint satisfaction affine Integer programming relaxations approximate graph colouring Sherali-Adams linear programming relaxations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

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)