The Setting
The comparison between sensitivity and block sensitivity asks how a Boolean function’s response to single coordinate changes constrains its response to changes on disjoint blocks. Let be a finite coordinate set and let . A total Boolean function on is a function , defined at every input. A total Boolean function is nonconstant if it takes different values at two inputs.
For an input and a block , the block flip is the input obtained by complementing exactly the coordinates in , as in (1); here denotes the complement of a Boolean value . (1)✦
The pointwise sensitivity of at is the number of coordinates whose individual flips change its value, and the sensitivity of is the maximum of this number over inputs, as in (2). (2)
The pointwise block sensitivity of at is the largest number of pairwise disjoint nonempty blocks whose flips each change its value; the block sensitivity of is its maximum over inputs, as in (3). (3)
For a positive integer , write for its coordinate set and for the all-false input.
The Claim
Theorem 1. For every real , there exist a positive integer and a nonconstant total Boolean function with such that (4)✦ For every integer , there exist a positive integer and a nonconstant total Boolean function with such that (5)✦
In the paper, the result reads: for every real , there are a positive integer and a nonconstant total Boolean function such that , and, more precisely, for every integer , the construction gives a nonconstant total Boolean function with .
What Is Checked
The claims (4) and (5) concern nonconstant total Boolean functions on a positive number of coordinates whose value at the all-false input is .