Approximate graph colouring and the hollow shadow

DOI10.1145/3564246.3585112WikidataQ130994122 ScholiaQ130994122MaRDI QIDQ6499253

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

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Constrained $(0,1)$-matrix completion with a staircase of fixed zeros
Zero-one matrices with zero trace
Transportation matrices with staircase patterns and majorization
Integral matrices with given row and column sums
Patterns that allow given row and column sums
Arc colorings of digraphs
An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
The collapse of the bounded width hierarchy
Improved Hardness of Approximating Chromatic Number
Inapproximability of Combinatorial Problems via Small LPs and SDPs
Lower Bounds on the Size of Semidefinite Programming Relaxations
Approximation Resistance from Pairwise-Independent Subgroups
Approximate Constraint Satisfaction Requires Large LP Relaxations
Coloring 3-Colorable Graphs with Less than n ^1/5 Colors
Constraint Satisfaction Problems Solvable by Local Consistency Methods
A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
Conditional Hardness for Approximate Coloring
On the power of unique 2-prover 1-round games
Improving the performance guarantee for approximate graph coloring
Class of global minimum bounds of polynomial functions
Properties of a Class of (0,1)-Matrices Covering a given Matrix
The Complexity of Near-Optimal Graph Coloring
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
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
Reducibility among Combinatorial Problems
Algebraic Approach to Promise Constraint Satisfaction
The Complexity of Promise SAT on Non-Boolean Domains
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
A Proof of the CSP Dichotomy Conjecture
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems
CSP gaps and reductions in the lasserre hierarchy
Towards a proof of the 2-to-1 games conjecture?
On non-optimally expanding sets in Grassmann graphs
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs
$(2+\varepsilon)$-Sat Is NP-hard
New hardness results for graph and hypergraph colorings
The complexity of satisfiability problems
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Rainbow Coloring Hardness via Low Sensitivity Polymorphisms
CLAP: A New Algorithm for Promise CSPs
Topology and Adjunction in Promise Constraint Satisfaction
Matrices of zeros and ones with given line sums and a zero block
On the hardness of approximating the chromatic number
Optimal inapproximability of satisfiable k-LIN over non-abelian groups
Pseudorandom sets in Grassmann graph have near-perfect expansion
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