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