  In this work, we study the parity complexity measures
${\mathsf{C}^{\oplus}_{\min}}[f]$ and ${\mathsf{DT^{\oplus}}}[f]$.
${\mathsf{C}^{\oplus}_{\min}}[f]$ is the \emph{parity kill number} of $f$, the
fewest number of parities on the input variables one has to fix in order to
"kill" $f$, i.e. to make it constant. ${\mathsf{DT^{\oplus}}}[f]$ is the depth
of the shortest \emph{parity decision tree} which computes $f$. These
complexity measures have in recent years become increasingly important in the
fields of communication complexity \cite{ZS09, MO09, ZS10, TWXZ13} and
pseudorandomness \cite{BK12, Sha11, CT13}.
  Our main result is a composition theorem for ${\mathsf{C}^{\oplus}_{\min}}$.
The $k$-th power of $f$, denoted $f^{\circ k}$, is the function which results
from composing $f$ with itself $k$ times. We prove that if $f$ is not a parity
function, then ${\mathsf{C}^{\oplus}_{\min}}[f^{\circ k}] \geq
\Omega({\mathsf{C}_{\min}}[f]^{k}).$ In other words, the parity kill number of
$f$ is essentially supermultiplicative in the \emph{normal} kill number of $f$
(also known as the minimum certificate complexity).
  As an application of our composition theorem, we show lower bounds on the
parity complexity measures of $\mathsf{Sort}^{\circ k}$ and $\mathsf{HI}^{\circ
k}$. Here $\mathsf{Sort}$ is the sort function due to Ambainis \cite{Amb06},
and $\mathsf{HI}$ is Kushilevitz's hemi-icosahedron function \cite{NW95}. In
doing so, we disprove a conjecture of Montanaro and Osborne \cite{MO09} which
had applications to communication complexity and computational learning theory.
In addition, we give new lower bounds for conjectures of \cite{MO09,ZS10} and
\cite{TWXZ13}.
