Efficient Simplification: The (im)possibilities

Efficient Simplification: The (im)possibilities

Research

InterestsPublicationsTalksWorkshops and SchoolsPhD ThesisMasters Thesis

Efficient Simplification: The (im)possibilities

This was a tutorial about upper and lower bounds in kernelization back in 2010. While the upper bounds are mostly presented the same way, you might want to look up cross-composition for the lower bounds —while the ideas are similar, the terminology has evolved since. See the Kernelization book for a deep dive into both upper and lower bounds, and even coping strategies for lower bounds including Turing kernels and Lossy kernels.