A composition theorem for parity kill number

In this work, we study the parity complexity measures ${\mathsf{C}}_{\min }^{}[f]$ and $\mathsf{D}{\mathsf{T}}^{\oplus }[f]$. ${\mathsf{C}}_{\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{D}{\mathsf{T}}^{\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}}_{\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}).$Inotherwords,theparitykillnumberof$f$isessentiallysupermultiplicativeinthe\mathit{\text{normal}}killnumberof$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{S}\mathsf{o}\mathsf{r}\mathsf{t}}^{\circ k}$ and $$\mathsf{H}\mathsf{I}$^{\circ k}$\mathrm{.}Here$$\mathsf{S}\mathsf{o}\mathsf{r}\mathsf{t}$$ is the sort function due to Ambainis \cite{Amb06}, and $\mathsf{H}\mathsf{I}$ 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}.