Hardness of Approximate Coloring

The graph coloring problem is a notoriously hard problem for which we do not have efficient algorithms. A $k$-coloring of a graph is an assignment of "colors" from $\{1,\cdots, k\}$ such that the end points of every edge have different colors. Given a 3-colorable graph, the best known efficient algorithms output a $n^{0.2}$-coloring. It is known that efficient algorithms cannot find a $4$-coloring.  Hence there is a large gap  ($n^{0.2}$ vs 4) between what current algorithms can achieve and the hardness results known.
 
In this thesis, we improve the hardness results for graph coloring and its generalizations. We show the following results:
 
1. For the case of (almost) 3-colorable graph, we show hardness of finding a $2^{poly(log log n)}$-coloring, assuming a variant of the Unique Games Conjecture (UGC). 
 
2. For the case of 4-colorable 4-uniform hypergraphs, we show hardness of finding a $2^{(\log n)^{1/18}}$-coloring. 
 
3. For the problem of the approximating the covering number of CSPs  with non-odd predicates, we show hardness of approximation to any constant factor, assuming a variant of UGC.