Conditional Hardness for Approximate Coloring

We study the AprxColoring$(q,Q)$ problem: Given a graph $G$, decide whether $\chi(G)\le q$ or $\chi(G)\ge Q$. We present hardness results for this problem for any constants $3\le q<Q$. For $q\ge4$, 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 “${\rhd\hskip-0.5em<}$-shaped” variant of his conjecture. Previously no hardness result was known for $q=3$ and $Q\ge6$. 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.