= Block sensitivity
{title2=$\operatorname{bs}(f)$}
For an input $x$, count the largest family of pairwise disjoint nonempty sets of coordinates such that flipping each set individually changes the <Boolean function> value. Maximizing over inputs gives block sensitivity. Sensitive sets need not be contiguous and need not consist of single bits. The standard bounded-error <quantum query complexity> lower bound is $\Omega(\sqrt{\operatorname{bs}(f)})$. A certificate for $f(x)$ meets every sensitive set, so its size bounds their disjoint count.
Back to article page
