Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR11-116 | 17th August 2011 17:10

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

RSS-Feed




TR11-116
Authors: Andris Ambainis, Xiaoming Sun
Publication: 19th August 2011 04:51
Downloads: 3237
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint