A Composition Theorem for Parity Kill Number
Ryan W. O’Donnell, John C. Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan · 2014
In this work, we study the parity complexity measures pCmin[f] and PDT[f]. Pcmin[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. PDT[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 [1], [2], [3], [4] and pseudorandomness [5], [6], [7]. Our main result is a composition theorem for pCmin. 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 pCmin[f^{circ k}] geq Omega(Cmin[f]^{k}). In other words, the parity kill number of f is essentially super multiplicative 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^{circ k} and HI^{circ k}. Here sort is the sort function due to Ambainis [8], and HI is Kushilevitz's hemi-icosahedron function [9]. In doing so, we disprove a conjecture of Montanaro and Osborne [2] which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of [2], [3] and [4].