Tata Institute of Fundamental Research
Hardness of Approximate Coloring
Synopsis Seminar
Speaker:
Girish Varma
Date:
Tuesday, 10 Mar 2015, 16:00 to 17:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Girish Varma |
| Date: | Tuesday, 10 Mar 2015, 16:00 to 17:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
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.
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.