Abstract

In this talk, I will explain the miniaturization mapping between parameterized problems and classical problems. And I will show that it establishes the equivalence not only between parameterized time complexity and exponential time complexity but also between parameterized space complexity and the so-called linear space complexity. Therefore many lower bounds in parameterized complexity can be translated to classical complexity, and vice versa.

Video Recording