Karthik C. S.
Calvin Lab -- Room 116
In this talk we will see a framework to show inapproximability of parameterized problems. This framework generalizes the 'Distributed PCPs' framework recently introduced by Abboud et al. [FOCS'17]. By applying the gadget reductions given by Chalermsook et al. [FOCS'17] to this framework, we settle the inapproximability of parameterized dominating set under various time hypotheses.
Joint work with Bundit Laekhanukit and Pasin Manurangsi.
Preprint available at https://eccc.weizmann.ac.il/report/2017/186/