Block Sensitivity of Minterm-Transitive Functions

Details Block Sensitivity of Minterm-Transitive Functions Block Sensitivity of Minterm-Transitive Functions

2010-01-13

arxiv.org/abs/1001.2052v1

Computer Science

Computational Complexity

10 pages

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Block Sensitivity of Minterm-Transitive Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Block Sensitivity of Minterm-Transitive Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Block Sensitivity of Minterm-Transitive Functions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-566591