| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427815 | Information Processing Letters | 2011 | 4 Pages |
In this note, we give an explicit construction of a minterm-transitive Boolean function with block sensitivity O(n3/7)O(n3/7). This removes a log-factor from the previously known bounds by Xiaoming Sun [Block sensitivity of weakly symmetric functions, Theoret. Comput. Sci. 384 (1) (2007) 87–91] and by Andrew Drucker [Block sensitivity of minterm-transitive functions, Theoret. Comput. Sci. 412 (41) (2011) 5796–5801]. Due to the matching lower bound by Drucker, it is shown that the minimum achievable block sensitivity for non-constant minterm-transitive function is Θ(n3/7)Θ(n3/7).
► We construct a minterm-transitive function with block sensitivity O(n3/7)O(n3/7). ► This improves the previously known constructions by Sun and by Drucker. ► Due to the matching lower bound by Drucker, our result is asymptotically tight.
