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

Abstract

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

7 pages

References in corpus (1)

• Lecture Notes on Evasiveness of Graph Properties

Cited by in corpus (3)

• Low-Sensitivity Functions from Unambiguous Certificates
• A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
• Sensitivity versus Certificate Complexity of Boolean Functions