Abstract
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)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). 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)=Ω(N3/7)bs(f)=Ω(N3/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(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).
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)=Ω(N1/3)bs(f)=Ω(N1/3). He also showed that there exists such a function for which bs(f)=O(N3/7lnN)bs(f)=O(N3/7lnN). 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)=Ω(N3/7)bs(f)=Ω(N3/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(N3/7ln1/7N)bs(f)=O(N3/7ln1/7N).
Original language | English |
---|---|
Pages (from-to) | 5796-5801 |
Number of pages | 6 |
Journal | Theoretical Computer Science |
Volume | 412 |
Issue number | 41 |
DOIs | |
Publication status | Published - 2011 |