Weak Compositions and Polynomial Lower-Bounds for Kernelization

provides a mathematical framework to investigate how well problem instances can be compressed. In this talk, I will present new results regarding polynomial lower bounds for kernelization. First, I will show how to sharpen the previous lower bound machinery. Following this, I will explain how one can use this modified machinery to derive new polynomial kernelization lower bounds for some natural parameterized problems, which include set packing, set covering, clique packing, and hitting set with bounded occurrences.