On Block Sensitivity and Fractional Block Sensitivity

Abstract

We investigate the relation between the block sensitivity bs(f) and fractional block sensitivity fbs(f) complexity measures of Boolean functions. While it is known that fbs(f) = O(bs(f)²), the best known separation achieves \({\rm{fbs}}\left( f \right) = \left( {{{\left( {3\sqrt 2 } \right)}^{ - 1}} + o\left( 1 \right)} \right){\rm{bs}}{\left( f \right)^{3/2}}\). We improve the constant factor and show a family of functions that give fbs(f) = (6^−1/2 − o(1)) bs(f)^3/2.