The Setting
For a Boolean input on a finite coordinate set and a block , the block flip is the Boolean input obtained by complementing the coordinates in .✦ The local sensitivity of a Boolean function counts the coordinates whose individual flips change its value, as in (1). (1) For a family of Boolean predicates and a Boolean output , the side sensitivity is the maximum local sensitivity among predicates and inputs with output , with default value zero; its definition is (2). (2)✦
Write . A tournament on is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ A regular tournament with parameter is a tournament on with vertices and outdegree at every vertex.✦ A good labelling of by labels is a map such that, for every vertex set of size and every map , some satisfy and .✦
For a finite family of Boolean centres on , the union of Hamming balls of radius is the predicate defined by (3), where denotes Hamming distance. (3)✦ Let be a nonnegative integer, and set . For , the block indicator centre on is the Boolean input that is true exactly on block .✦ The initial Hamming family consists of the predicates in (4), indexed from . (4) The extension of a -predicate family is a collection of predicate families, one at each predicate count , defined by (5).✦ The construction base is the collection of predicate families defined by (5) with and the initial Hamming family from (4). (5)✦
For a finite base coordinate set , the tower coordinate sets are the products in (6). (6)✦ The iterated family of predicates on equals at depth zero; at successor depth it is the recursive predicate family formed from using and .✦ The tower side sensitivity is defined by (7), where is truncated at zero. (7)✦
The Claim
Theorem 1 (Quantitative sensitivity profiles). Let be a nonnegative integer.
For the coupled recurrence bound, let and . Suppose , and , and suppose the recurrences (8) hold. (8) Then the coupled recurrence estimate is (9). (9)✦
Let be nonnegative integers with , and put . Suppose . Let and be arrays of nonnegative integers with , and . Suppose the ordinary and joint profiles satisfy (10). (10) Then the two-sided sensitivity estimate is (11). (11)✦
Suppose and , and choose . Then (12) holds. (12)✦
Let be integers, let be a regular tournament with parameter , and let be a good labelling by labels. Use the construction base, and in (7). Suppose . Then the tower sensitivity estimate is (13). (13)✦
In the paper, the result reads: for and , with , , a regular tournament and labels satisfying the good labelling condition, every level satisfies and .
What Is Checked
The tower estimate (13) is stated over finite Boolean tower families with a regular tournament and good labels; the numerical estimates (11) and (9) concern arrays and real sequences satisfying their respective initial conditions and recurrences, and the budget estimate (12) concerns integers and .