Name
Abstract | ||
|---|---|---|
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 | DOI | Venue |
|---|---|---|
2018 | 10.1134/S1995080218070041 | Lobachevskii Journal of Mathematics |
Keywords | Field | DocType |
Query complexity, block sensitivity | Boolean function,Combinatorics,Mathematical analysis,Mathematics | Journal |
Volume | Issue | ISSN |
abs/1810.02393 | 7 | 1995-0802 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andris Ambainis | 1 | 2000 | 183.24 |
| Krisjanis Prusis | 2 | 13 | 3.63 |
| Jevgenijs Vihrovs | 3 | 10 | 3.92 |