Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR11-116 | 17th August 2011 17:10

New separation between $s(f)$ and $bs(f)$

TR11-116
Authors: Andris Ambainis, Xiaoming Sun
Publication: 19th August 2011 04:51
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=\frac{2}{3}s(f)^2-\frac{1}{3}s(f)$.