Speaker: |
Amey Bhangale (Dept. of Applied Math and Computer Science The Weizmann Institute of Science Ziskind building, Room 246 Rehovot, 76100 ISRAEL) |

Organiser: |
Prahladh Harsha |

Date: |
Tuesday, 3 Jul 2018, 14:00 to 15:00 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

We show that given a k-uniform hypergraph which is (k - 2\sqrt{k})-rainbow colorable, it is NP-hard to find a 2-coloring of it. This improves the result of Guruswami-Lee. We also show NP-hardness of finding a c-coloring of an approximate rainbow colorable (a slightly weaker notion than the rainbow coloring) hypergraph for large c (joint work with Per Austrin and Aditya Potukuchi).