Block sensitivity of minterm-transitive functions
Boolean functions with a high degree of symmetry are interesting from a complexity theory perspective: extensive research has shown that these functions, if nonconstant, must have high complexity according to various measures. In a recent work of this type, Sun (2007) [9] gave lower bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f) = Omega(N(1/3)). He also showed that there exists such a function for which bs(f) = O(N(3/7) ln N). His example belongs to a subclass of transitively invariant functions called "minterm-transitive" functions, defined by Chakraborty (2005) [3]. We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f) = Omega(N(3/7)). Thus, Sun's example has nearly minimal block sensitivity for this subclass. Second, we improve Sun's example: we exhibit a minterm-transitive function for which bs(f) = O(N(3/7) ln(1/7) N). (C) 2011 Elsevier B.V. All rights reserved.
block sensitivity minterm-transitive functions boolean functions transitively invariant functions weakly symmetric functions