On Block Sensitivity and Fractional Block Sensitivity
share
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)^2), the best known separation achieves fbs(f) = (1/3√(2) +o(1)) bs(f)^3/2. We improve the constant factor and show a family of functions that give fbs(f) = (1/√(6)-o(1)) bs(f)^3/2.
READ FULL TEXT