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