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

2011/08/17 by Andris Ambainis, Xiaoming Sun, Ambainis, Andris +1 · 1 citation
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #cs.CC

paper · pdf · doi:10.48550/arxiv.1108.3494

7 pages

arxiv created 2011/08/17 · arxiv updated 2011/08/18

Abstract

In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: bs(f)=(2/3)s(f)²-(1/3)s(f).

Cited by

• Block Sensitivity can exceed Spectral Sensitivity Squared

Related

• Sensitivity versus block sensitivity of Boolean functions
• On Block Sensitivity and Fractional Block Sensitivity
• New upper bound on block sensitivity and certificate complexity in terms of sensitivity
• On the Sensitivity Conjecture for Disjunctive Normal Forms
• On the Sensitivity of Cyclically-Invariant Boolean Functions