In this work, we study the parity complexity measures C+min[f] and DT+[f]. C+min[f] is the
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. DT+[f] is the depth of the shortest parity decision
tree which computes f. These complexity measures have in recent years become increasingly
important in the fields of communication complexity and pseudorandomness.
Our main result is a composition theorem for C+min. The k-th power of f, denoted f^k, is the
function which results from composing f with itself k times. We prove that if f is not a parity
function, then
C+min[f^k] >= \Omega(Cmin[f]^k).
In other words, the parity kill number of f is essentially supermultiplicative in the 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 Sort^k and HI^k. Here Sort is the sort function due to Ambainis,
and HI is Kushilevitz's hemi-icosahedron function. In doing so, we disprove a conjecture
of Montanaro and Osborne which had applications to communication complexity
and computational learning theory. In addition, we give new lower bounds for conjectures given by Montanaro and Osborne.
*
*