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

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 hemiicosahedron 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 