
Boolean functions with symmetry properties 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 recent work of this type, Sun gave 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}), and that there exists such a function for which bs(f) = O(N^{3/7}ln N). His example function belongs to a subclass of transitively invariant functions called the minterm-transitive functions (defined in earlier work by Chakraborty). 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 function has nearly minimal block sensitivity for this subclass. Second, we give an improved example: a minterm-transitive function for which bs(f) = O(N^{3/7}ln^{1/7}N).
10 pages
FOS: Computer and information sciences, Weakly symmetric functions, Minterm-transitive functions, block sensitivity, minterm-transitive functions, Block sensitivity, Transitively invariant functions, weakly symmetric functions, Computational Complexity (cs.CC), Theoretical Computer Science, Computer Science - Computational Complexity, transitively invariant functions, Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), Boolean functions, Computer Science(all)
FOS: Computer and information sciences, Weakly symmetric functions, Minterm-transitive functions, block sensitivity, minterm-transitive functions, Block sensitivity, Transitively invariant functions, weakly symmetric functions, Computational Complexity (cs.CC), Theoretical Computer Science, Computer Science - Computational Complexity, transitively invariant functions, Switching theory, application of Boolean algebra; Boolean functions, Complexity classes (hierarchies, relations among complexity classes, etc.), Boolean functions, Computer Science(all)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
