On Block Sensitivity and Fractional Block Sensitivity
- 作者: Ambainis A.1, Prūsis K.1, Vihrovs J.1
-
隶属关系:
- Faculty of Computing
- 期: 卷 39, 编号 7 (2018)
- 页面: 967-969
- 栏目: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202733
- DOI: https://doi.org/10.1134/S1995080218070041
- ID: 202733
如何引用文章
详细
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.
作者简介
A. Ambainis
Faculty of Computing
编辑信件的主要联系方式.
Email: andris.ambainis@lu.lv
拉脱维亚, Raiņa bulv. 19, Rīga, LV-1586
K. Prūsis
Faculty of Computing
Email: andris.ambainis@lu.lv
拉脱维亚, Raiņa bulv. 19, Rīga, LV-1586
J. Vihrovs
Faculty of Computing
Email: andris.ambainis@lu.lv
拉脱维亚, Raiņa bulv. 19, Rīga, LV-1586
![](/img/style/loading.gif)