The Setting
Sensitivity and block sensitivity describe how a total Boolean function reacts to changes in its input coordinates. The distinction is between changing one coordinate at a time and allowing disjoint sets of coordinates.
The Definition
Definition 1. Let be a coordinate set, let , and let be a total Boolean function. For an input and a finite set , the block flip is defined by (1), where denotes Boolean negation: (1)✦
Suppose that is finite. The pointwise sensitivity of at is the number of coordinates whose singleton flips change its value, as in (2): (2)✦ The sensitivity of is its maximum pointwise sensitivity, as in (3): (3)✦
The pointwise block sensitivity of at is the largest number of pairwise disjoint nonempty blocks whose flips change its value, as in (4): (4)✦ The block sensitivity of is its maximum pointwise block sensitivity, as in (5): (5)✦
In the paper, the result reads: for a positive integer and a total Boolean function on , flips precisely the coordinates of , counts coordinates with and is its maximum over , while is the largest size of a family of pairwise disjoint nonempty coordinate sets whose flips change at and is its maximum over .
What Is Checked
Block flips are defined for finite subsets of any coordinate set; sensitivity and block sensitivity are defined for total Boolean functions on a finite coordinate set.