Theory Seminar

Reversing Color Coding

Karthik C. S.Rutgers University

(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.


Greg Bodwin


Euiwoong Lee