Speaker: Yu Zhao Carnegie Mellon University
Time: 2015-12-28 14:30-2015-12-28 15:30
Venue: FIT 1-222

Abstract:

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.

Short Bio:

Yu Zhao is a first-year Ph.D. student at CMU. My advisor is Ryan O'Donnell. I am broadly interested in algorithm and complexity theory.

http://www.cs.cmu.edu/~yuzhao1/