The Setting
The initial stage asks how much sensitivity a Hamming ball family can have on each output side, and how much two of its predicates can share.
Let be a finite coordinate set, and let an input assign false or true to each coordinate. The block flip of along a subset is the input specified in (1), where denotes Boolean complementation. (1)✦ For a Boolean function on , the local sensitivity is the number of coordinates whose individual flip changes its value, as in (2). (2)✦ The local joint sensitivity of two Boolean functions on is the number of coordinates sensitive for both at , as in (3). (3)✦
For a family of Boolean predicates on and a Boolean value , the side sensitivity is the maximum local sensitivity at inputs with output , taken over the family, as in (4). (4)✦ The joint sensitivity is the maximum local joint sensitivity of two distinct predicates at an input where both have output , as in (5). (5)✦
Let be a family of Boolean centers on , indexed by a finite set , and write for Hamming distance. The union of Hamming balls of nonnegative integer radius about a family of Boolean centers on is the Boolean predicate defined by (6). (6) For an input on and a nonempty family of Boolean centers on , the nearest center distance is the minimum Hamming distance from to a center, as in (7). (7)✦
Fix nonnegative integers , put , and take the coordinate set . The block indicator center on , for , is the Boolean input defined by (8). (8) The initial Hamming family on is the family of Boolean predicates in (9), with . (9)✦ Its nesting is in the predicate index . Write and for its ordinary and joint profiles.
The Claim
Theorem 1. Let be nonnegative integers and . The initial family has the false-side bound (10), the true-side bound (11), and the joint profile (12) for either Boolean value : (10)✦ (11)✦ (12)✦
Let be a finite family of Boolean centers on a finite coordinate set , and let be a nonnegative integer. Suppose distinct centers satisfy whenever . At any input with , the local sensitivity satisfies (13): (13)✦
For any nonempty finite family of Boolean centers on a finite coordinate set , every input and coordinate satisfy (14): (14)✦
In the paper, the result reads: for and , with , , , and .
What Is Checked
The initial profile statements concern the initial Hamming family (9) for all nonnegative ; the Hamming ball statements concern finite coordinate sets and finite center families, with separation in (13) and nonemptiness in (14).