June 25, 2019, 10:15 a.m.
Title: Parameterized Inapproximability
Speaker: Pasin Manurangsi
Time and Place: Tuesday, 25th of June 2019, 10:15 am, room 310
Abstract: The area of parameterized complexity seeks a more fine-grained understanding of NP-hard problems by relaxing the notion of efficient algorithms to the so-called fixed-parameter tractability (FPT). After more than two decades of work, the parameterized complexity of many fundamental problems have been classified; that is, each problem is either shown to be in FPT or shown to be hard for some complexity class that is believed to not be in FPT. However, for most problems not in FPT, their approximability statuses remain open. Specifically, there were few techniques to prove hardness of approximation in the parameterized regime. This has somewhat changed in the last few years where more tools have been developed to tackle such problems. In this talk, I will survey some these recent developments and interesting questions that remain open.