Computer Science – Computational Complexity
Scientific paper
2010-08-03
Computer Science
Computational Complexity
5 pages, no figures
Scientific paper
Determining the maximal separation between sensitivity and block sensitivity of Boolean functions is of interest for computational complexity theory. We construct a sequence of Boolean functions with bs(f) = 1/2 s(f)^2 + 1/2 s(f). The best known separation previously was bs(f) = 1/2 s(f)^2 due to Rubinstein. We also report results of computer search for functions with at most 12 variables.
No associations
LandOfFree
Sensitivity versus block sensitivity of Boolean 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 Sensitivity versus block sensitivity of Boolean functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sensitivity versus block sensitivity of Boolean functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-614841