Talks
Fall 2015

An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
Friday, November 6th, 2015, 2:00 pm–2:30 pm
Speaker:
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.