Conditional Hardness for Approximate Coloring

DOI10.1137/07068062XzbMath1192.68317MaRDI 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 coloring; hardness of approximation; unique games

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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