BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/491
DTSTAMP:20230914T125926Z
SUMMARY:Hardness of Hypergraph Coloring
DESCRIPTION:Speaker: Girish Varma\n\nAbstract: \nAbstract: The Graph Colori
ng problem is to efficiently color the vertices of a graph on n vertices
using as few colors as possible such that no edge is monochromatic. All
known efficient algorithms till date\, only guarantee a $n^\\delta$ colo
ring\, when the input is promised to be 3 colorable. However what is kno
wn is that it is NP Hard to 4 color a 3 colorable graph. Improving the har
dness result to match the algorithms has been an open question for long. H
owever progress had been made in the hypergraph version: Given a 2 colorab
le hypergraph\, prove that its hard to color it using Q colors. The resul
ts currently known only give hardness for upto $Q= log^c n$. We give the f
irst results that crosses the log^c barrier using the low-degree polynomi
al code (aka\, the 'short code' of Barak et. al. [FOCS 2012]) and the tech
niques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this cod
e for inapproximability results. In particular\, we prove quasi-NP-hardnes
s of the following problems on n-vertex hyper-graphs: \n* Coloring a 2-co
lorable 8-uniform hypergraph with 2^2^Ω(√loglogn) colors. \n* Coloring
a 4-colorable 4-uniform hypergraph with 2^2^Ω(√loglogn) colors. \n* C
oloring a 3-colorable 3-uniform hypergraph with (logn)^Ω(1/logloglogn) co
lors. \n \nReference : http://arxiv.org/abs/1311.7407\n
URL:https://www.tcs.tifr.res.in/web/events/491
DTSTART;TZID=Asia/Kolkata:20140523T100000
DTEND;TZID=Asia/Kolkata:20140523T110000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR