6533b7d9fe1ef96bd126ca42
RESEARCH PRODUCT
New separation between $s(f)$ and $bs(f)$
Andris AmbainisXiaoming Sunsubject
FOS: Computer and information sciencesComputational Complexity (cs.CC)description
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=(2/3)s(f)^2-(1/3)s(f)$.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-01-01 |