Sensitivity cite{CD82,CDR86} and block sensitivity cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexity, the Sensitivity versus Block Sensitivity question, proposed by Nisan and Szegedy cite{Nisan94} in 1992, is whether these two complexity measures are polynomially related, i.e., whether $bs(f)=O(s(f)^{O(1)})$. We prove an new upper bound on block sensitivity in terms of sensitivity: $bs(f) leq 2^{s(f)-1} s(f)$. Previously, the best upper bound on block sensitivity was $bs(f) leq (frac{e}{sqrt{2pi}}) e^{s(f)} sqrt{s(f)}$ by Kenyon and Kutin cite{KK}. We also prove that if $min{s_0(f),s_1(f)}$ is a constant, then sensitivity and block sensitivity are linearly related, i.e. $bs(f)=O(s(f))$.
Download