We introduce a new form of composition called weak composition that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \mathbb{N}$ be two parameterized problems where the unparameterized version of $L_1$ is NP-hard. Assuming $coNP \not\subseteq NP/poly$, our framework essentially states that composing $t$ $L_1$-instances each with parameter $k$, to an $L_2$-instance with parameter $k' \leq t^{1/d}k^{O(1)}$, implies that $L_2$ does not have a kernel of size $O(k^{d-\varepsilon})$ for any $\varepsilon > 0$. We show two examples of weak composition and derive polynomial kernelization lower bounds for $d$-Bipartite Regular Perfect Code and $d$-Dimensional-Matching, parameterized by the solution size $k$. By reduction using linear parameter transformation, we then derive the following lower-bounds for kernel sizes when the parameter is the solution size $k$ (assuming $coNP \not\subseteq NP/poly$):

- $d$-Set Packing, $d$-Set Cover, $d$-Exact Set Cover, Hitting Set with $d$-Bounded Occurrences, and Exact Hitting Set with $d$-Bounded Occurrences have no kernels of size $O(k^{d-3-\varepsilon})$ for any $\varepsilon > 0$.

- $K_d$ Packing and Induced $K_{s,d}$ Packing for any constant $s \ge 1$ have no kernels of size $O(k^{d-4-\varepsilon})$ for any $\varepsilon > 0$.

- $d$-Red-Blue Dominating Set and $d$-Steiner Tree have no kernels of sizes $O(k^{d-3-\varepsilon})$ and $O(k^{d-4-\varepsilon})$, respectively, for any $\varepsilon > 0$.

Our results give a negative answer to an open question raised by Dom, Lokshtanov, and Saurabh~[ICALP2009] regarding the existence of uniform polynomial kernels for the problems above. All our lower bounds transfer automatically to compression lower bounds, a notion defined by Harnik and Naor~[SICOMP2010] to study the compressibility of NP instances with cryptographic applications. We believe weak composition can be used to obtain polynomial kernelization lower bounds for other interesting parameterized problems.

In the last part of the paper we strengthen previously known super-polynomial kernelization lower bounds to super-quasi-polynomial lower bounds, by showing that quasi-polynomial kernels for compositional NP-hard parameterized problems implies the collapse of the exponential hierarchy. These bounds hold even the kernelization algorithms are allowed to run in quasi-polynomial time.

Add lower bounds for d-dimensional matching, and super-quasipolynomial lower bounds.

We introduce a new form of composition called \emph{weak composition} that allows us to obtain polynomial kernelization lower-bounds for several natural parameterized problems. Let $d \ge 2$ be some constant and let $L_1, L_2 \subseteq \{0,1\}^* \times \N$ be two parameterized problems where the unparameterized version of $L_1$ is \NP-hard. Assuming $\coNP \not\subseteq \NP/\poly$, our framework essentially states that composing $t$ $L_1$-instances each with parameter $k$, to an $L_2$-instance with parameter $k' \leq t^{1/d}k^{O(1)}$, implies that $L_2$ does not have a kernel of size $O(k^{d-\varepsilon})$ for any $\varepsilon > 0$. Using this tool, we derive the following lower-bounds for kernel sizes when the parameter is the solution size $k$ (assuming $\coNP \not\subseteq \NP/\poly$):

\begin{itemize}
\item \textsc{$d$-Set Packing}, \textsc{$d$-Set Cover}, \textsc{$d$-Exact Set Cover}, \textsc{Hitting Set with $d$-Bounded Occurrences}, and \textsc{Exact Hitting Set with $d$-Bounded Occurrences} have no kernels of size $O(k^{d-3-\varepsilon})$ for any $\varepsilon > 0$.

\item \textsc{$K_d$ Packing} and \textsc{Induced $K_{1,d}$ Packing} have no kernels of size $O(k^{d-4-\varepsilon})$ for any $\varepsilon > 0$.

\item \textsc{$d$-Red-Blue Dominating Set} and \textsc{$d$-Steiner Tree} have no kernels of sizes $O(k^{d-3-\varepsilon})$ and $O(k^{d-4-\varepsilon})$, respectively, for any $\varepsilon > 0$.
\end{itemize}

To obtain these lower-bounds, we first prove kernel lower bound for the \textsc{$d$-Bipartite Regular Perfect Code} parameterized by the solution size $k$, and then reduce from it using linear parametric transformations. Our results give a negative answer to an open question raised by Dom, Lokshtanov, and Saurabh~[ICALP2009] regarding the existence of \emph{uniform polynomial kernel} for the problems above. Up to a polylogarithmic factor, all our lower bounds transfer automatically to compression lower bounds, a notion defined by Harnik and Naor~[SICOMP2010] to study the compressibility of \NP\ instances with cryptographic applications. We believe weak composition can be used to obtain polynomial kernelization lower bounds for other interesting parameterized problems.