For 3qQ we consider the ApproxColoring(qQ) problem of deciding for a given graph G whether (G)q or (G)Q . It was show in [DMR06] that the problem ApproxColoring(qQ) is NP-hard for q=34 and arbitrary large constant Q under variants of the Unique Games Conjecture.

In this paper we give a tighter analysis of the reduction of [DMR06] from Unique Games to the ApproxColoring problem. We find that (under appropriate conjecture) a careful calculation of the parameters in [DMR06] implies hardness of coloring a 4-colorable graph with logc(log(n)) colors for some positive constant c. By improving the analysis of the reduction we show hardness of coloring a 4-colorable graph with logc(n) colors for some positive constant c.

The main technical contribution of the paper is a variant of the Majority is Stablest Theorem, which says that among all balanced functions in which every coordinate has o(1) influence, the Majority function has the largest noise stability. We adapt the theorem for our applications to get a better dependency between the parameters required for the reduction.