Karthik C.S., Rutgers University

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 the talk.

Joint work with Boris Bukh and Bhargav Narayanan.

Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://theory.cs.rutgers.edu/theory_seminar