On Block Sensitivity and Fractional Block Sensitivity

Andris Ambainis, Krišjānis Prūsis, Jevgēnijs Vihrovs

We investigate the relation between the block sensitivity $\text{bs}(f)$ and fractional block sensitivity $\text{fbs}(f)$ complexity measures of Boolean functions. While it is know…