Key points are not available for this paper at this time.
We study the AprxColoring (q, Q) problem: Given a graph G, decide whether (G) q or (G) Q. We present hardness results for this problem for any constants 3 q<Q. For q4, 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 “-0. 5em<-shaped” variant of his conjecture. Previously no hardness result was known for q=3 and Q6. 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.
Dinur et al. (Thu,) studied this question.