Conditional Hardness for Approximate Coloring

DOI10.1137/07068062XzbMath1192.68317OpenAlexW2047861934MaRDI QIDQ3575151

Elchanan Mossel, Irit Dinur, Oded Regev

Publication date: 7 July 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/07068062x

zbMATH Keywords

graph coloringhardness of approximationunique games

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (34)

Topology and Adjunction in Promise Constraint Satisfaction ⋮ Bounds on 2-query locally testable codes with affine tests ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Unnamed Item ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank ⋮ Pseudorandom sets in Grassmann graph have near-perfect expansion ⋮ Bi-Covering: Covering Edges with Two Small Subsets of Vertices ⋮ Unnamed Item ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes ⋮ Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors ⋮ High dimensional Hoffman bound and applications in extremal combinatorics ⋮ Unnamed Item ⋮ On percolation and ‐hardness ⋮ Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder ⋮ Kneser graphs are like Swiss cheese ⋮ Linear Index Coding via Semidefinite Programming ⋮ Query-Efficient Dictatorship Testing with Perfect Completeness ⋮ Unnamed Item ⋮ Approximately coloring graphs without long induced paths ⋮ Unnamed Item ⋮ Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Hypergraph list coloring and Euclidean Ramsey theory ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Simultaneous max-cut is harder to approximate than max-cut ⋮ The Quest for Strong Inapproximability Results with Perfect Completeness ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Beyond PCSP (\textbf{1-in-3}, \textbf{NAE}) ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs

This page was built for publication: Conditional Hardness for Approximate Coloring