Abstract: 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.
