Conditional hardness for approximate coloring

Irit Dinur, Elchanan Mossel, Oded Regev

Research output: Contribution to journalArticlepeer-review


We study the AprxColoring(q, Q) problem: Given a graph G, decide whether x(G)≤ q or x(G) ≥ Q. We present hardness results for this problem for any constants 3 ≤ q <Q. For q ≥4, our result is based on Khot's 2-to-1 label cover, which is conjectured to be NP-hard [S. Khot, Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767-775]. For q = 3, we base our hardness result on a certain "⋉-shaped" variant of his conjecture. Previously no hardness result was known for q = 3 and Q ≥ 6. At the heart of our proof are tight bounds on generalized noise-stability quantities, which extend the recent work of Mossel, O'Donnell, and Oleszkiewicz ["Noise stability of functions with low influences: Invariance and optimality, " Ann. of Math. (2), to appear] and should have wider applicability.

Original languageEnglish (US)
Pages (from-to)843-873
Number of pages31
JournalSIAM Journal on Computing
Issue number3
StatePublished - 2009


  • Graph coloring
  • Hardness of approximation
  • Unique games

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Conditional hardness for approximate coloring'. Together they form a unique fingerprint.

Cite this