2010/08/03 by Madars Virza, Virza, Madars
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.1008.0521
5 pages, no figures
arxiv created 2010/12/08 · arxiv updated 2010/12/09
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.