# Hardness of Approximate Coloring

Speaker:

## Time:

Tuesday, 10 March 2015, 16:00 to 17:00

## Venue:

• D-405 (D-Block Seminar Room)
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.