6533b823fe1ef96bd127ecd1
RESEARCH PRODUCT
On Block Sensitivity and Fractional Block Sensitivity
Andris AmbainisJevgēnijs VihrovsKrišjānis Prūsissubject
FOS: Computer and information sciencesGeneral Mathematics010102 general mathematicsBlock (permutation group theory)0102 computer and information sciencesComputational Complexity (cs.CC)01 natural sciencesConstant factorCombinatoricsComputer Science - Computational Complexity010201 computation theory & mathematicsSensitivity (control systems)0101 mathematicsAlgebra over a fieldMathematicsdescription
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 $${\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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2018-10-04 |