BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/585
DTSTAMP:20230914T125930Z
SUMMARY:Hardness of Approximate Coloring
DESCRIPTION:Speaker: Girish Varma\n\nAbstract: \nAbstract: The graph color
ing problem is a notoriously hard problem for which we do not have efficie
nt 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 differ
ent colors. Given a 3-colorable graph\, the best known efficient algorith
ms output a $n^{0.2}$-coloring. It is known that efficient algorithms cann
ot find a $4$-coloring. Hence there is a large gap ($n^{0.2}$ vs 4) b
etween what current algorithms can achieve and the hardness results known.
\n \nIn this thesis\, we improve the hardness results for graph coloring
and its generalizations. We show the following results:\n \n1. For the ca
se 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). \n \n2. For the case of 4-colorable 4-uniform hypergraphs\, we
show hardness of finding a $2^{(\\log n)^{1/18}}$-coloring. \n \n3. For
the problem of the approximating the covering number of CSPs with non-o
dd predicates\, we show hardness of approximation to any constant factor\,
assuming a variant of UGC.\n
URL:https://www.tcs.tifr.res.in/web/events/585
DTSTART;TZID=Asia/Kolkata:20150310T160000
DTEND;TZID=Asia/Kolkata:20150310T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR