Fall 2018

A Framework for Parameterized Hardness of Approximation

Friday, August 31st, 2018, 10:30 am12: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