MENU 
Theory Seminar
Reversing Color Coding
Karthik C. S.Rutgers University
WHEN:
Friday, September 10, 2021 @ 3:00 pm - 4:00 pm
This event is free and open to the publicAdd to Google Calendar
This event is free and open to the publicAdd to Google Calendar
WEB: Event Website
SHARE:
(Joint with Purdue. Please follow the Event Website link.)
Abstract: In computational complexity it is often easier to prove hardness results for a colored version of a combinatorial or graph theoretic problem than its uncolored counterpart. Moreover, one can typically reduce from the uncolored version of a problem to its colored counterpart by a straightforward application of the celebrated color coding technique. Is the reduction in the reverse direction also possible?
In some interesting cases, such as the parameterized set intersection problem, such a reduction is highly non-trivial and this shall be the focus of this talk.
Joint work with Boris Bukh and Bhargav Narayanan.