  Parallel fixed-parameter tractability studies how parameterized problems can
be solved in parallel. A surprisingly large number of parameterized problems
admit a high level of parallelization, but this does not mean that we can also
efficiently compute small problem kernels in parallel: known kernelization
algorithms are typically highly sequential. In the present paper, we establish
a number of upper and lower bounds concerning the sizes of kernels that can be
computed in parallel. An intriguing finding is that there are complex
trade-offs between kernel size and the depth of the circuits needed to compute
them: For the vertex cover problem, an exponential kernel can be computed by
AC$^0$-circuits, a quadratic kernel by TC$^0$-circuits, and a linear kernel by
randomized NC-circuits with derandomization being possible only if it is also
possible for the matching problem. Other natural problems for which similar
(but quantitatively different) effects can be observed include tree
decomposition problems parameterized by the vertex cover number, the undirected
feedback vertex set problem, the matching problem, or the point line cover
problem. We also present natural problems for which computing kernels is
inherently sequential.
