TR11-116 Authors: Andris Ambainis, Xiaoming Sun

Publication: 19th August 2011 04:51

Downloads: 1398

Keywords:

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