Minterm-transitive functions with asymptotically smallest block sensitivity

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.