BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/887
DTSTAMP:20230914T125942Z
SUMMARY:Improved NP-hardness of Hypergraph Rainbow Coloring
DESCRIPTION:Speaker: Amey Bhangale (Dept. of Applied Math and Computer Scie
nce\nThe Weizmann Institute of Science\nZiskind building\, Room 246\nRehov
ot\, 76100 ISRAEL)\n\nAbstract: \nA k-uniform hypergraph is defined to be
q-rainbow colorable (q\\leq k) if there exists a coloring of the vertex se
t with q colors such that every hyperedge contains all the q colors. Given
a k-uniform hypergraph which is q rainbow colorable for some q\, can we a
t least find a 2 coloring in polynomial time? This problem comes under the
so called *promise* constraint satisfaction problems.\nWe show that given
a k-uniform hypergraph which is (k - 2\\sqrt{k})-rainbow colorable\, it i
s NP-hard to find a 2-coloring of it. This improves the result of Guruswam
i-Lee. We also show NP-hardness of finding a c-coloring of an approximate
rainbow colorable (a slightly weaker notion than the rainbow coloring) hyp
ergraph for large c (joint work with Per Austrin and Aditya Potukuchi).\n
URL:https://www.tcs.tifr.res.in/web/events/887
DTSTART;TZID=Asia/Kolkata:20180703T140000
DTEND;TZID=Asia/Kolkata:20180703T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR