Events
Fall 2018

A Framework for Parameterized Hardness of Approximation

Aug 31, 2018 10:30 am – 12:00 pm 

Add to Calendar

Speaker: 

Karthik C. S.

Location: 

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/