Fall 2018

A Framework for Parameterized Hardness of Approximation

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

Add to Calendar


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