2013/12/07 by Ryan O’Donnell, Xiaorui Sun, O'Donnell, Ryan +7 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1312.2143
openalex publication_date 2013/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we study the parity complexity measures C⊕min[f] and \mathsfDT⊕[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. \mathsfDT⊕[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 \citeZS09, MO09, ZS10, TWXZ13 and pseudorandomness \citeBK12, Sha11, CT13. 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] ≥ Ω(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 \citeAmb06, and HI is Kushilevitz's hemi-icosahedron function \citeNW95. In doing so, we disprove a conjecture of Montanaro and Osborne \citeMO09 which had applications to communication complexity and computational learning theory. In addition, we give new lower bounds for conjectures of \citeMO09,ZS10 and \citeTWXZ13.