Improved hardness results for approximating the chromatic number

First, a simplified geometric proof is presented for the result of Lund and Yannakakis saying that for some ε > 0 it is NP-hard to approximate the chromatic number of graphs with N vertices by a factor of N^ε. Then, more sophisticated techniques are employed to improve the exponent. A randomized twisting method allows us to completely pack a certain space with copies of a graph without much affecting the independence number. Together with the newest results of Bellare, Goldreich and Sudan on the number of amortized free bits, it is shown that for every ε > 0 the chromatic number cannot be approximated by a factor of N^1/5-ε unless NP = ZPP. Finally, we get polynomial lower bounds in terms of x. Unless NP = ZPP, the performance ratio of every polynomial time algorithm approximating the chromatic number of x-colorable graphs (i.e., the chromatic number is at most x) is at least x^{1/5 - o(1)} (where the o-notation is with respect to x).