New upper bound on block sensitivity and certificate complexity in terms of sensitivity

Abstract

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)\le 2^{s(f)-1}s(f)$. Previously, the best upper bound on block sensitivity was $bs(f)\le (\frac{e}{\sqrt{2\pi }})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))$.

9 pages

References in corpus (1)

• Variations on the Sensitivity Conjecture