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

Andris Ambainis, Yihan Gao, Jieming Mao +2

Sensitivity \cite{CD82,CDR86} and block sensitivity \cite{Nisan91} are two important complexity measures of Boolean functions. A longstanding open problem in decision tree complexi…