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)

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.