Talks
Fall 2015

An Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space

Friday, November 6th, 2015, 2:00 pm2:30 pm

Add to Calendar

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.