Graduate Students
Graduate Programs     
Graduate Home Ph D Programs Masters Degree Ph D Program Requirements Course Descriptions Current Courses Admissions Current Graduate Students Graduate Student Seminar SIAM Chapter Seminar Recent Graduates Incoming Students

Apply Now
Graduate Seminar

Yu Zhao
Carnegie Mellon University
Title: A composition theorem for parity kill number

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] \geq \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.

Date: Thursday, February 12, 2015
Time: 5:30 pm
Location: Wean Hall 8220
Submitted by:  Zilin Jiang