The Setting
Let be a finite coordinate set and let . For an input and a block , the block flip is the input obtained by complementing the coordinates in : (1)✦ Here interchanges false and true. The pointwise sensitivity of a Boolean function is the number of coordinates whose individual flip changes its value, using the block flip in (1): (2)✦
Write , with , and let be a family of Boolean predicates on . A nested predicate family on is a family in which truth of a predicate at an index forces truth at every smaller index; nesting therefore concerns the predicate index rather than monotonicity in the input bits.✦ The profiles below are defined for arbitrary families, including families without nesting.
For the iterated families, let and be the numbers of vertices and available edge labels, respectively, and let be a tournament on , a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.✦ An edge labelling of the tournament is a function . The tower coordinate sets are the finite sets defined recursively by (3)✦ Choose a base family of predicates on for every nonnegative integer . The iterated predicate family is a family of predicates on : at level zero it is , and at level it is the tournament recursion, with tournament and labelling , applied to , on the coordinate sets in (3).✦
For a nonnegative total height , write and . Let denote the final level under consideration.
The Claim
Definition 1 (Nested families and sensitivity profiles). (4)✦ For Boolean functions , their local joint sensitivity at is the number (5)✦ For a family of Boolean predicates on and a Boolean value , the side sensitivity is the maximum pointwise sensitivity in (2) over predicates and inputs with output , with maximum zero when there are no such inputs: (6)✦ For a family of Boolean predicates on and a Boolean value , the joint sensitivity is the maximum local joint sensitivity from (5) over pairs of distinct predicates that both have output at a common input, with maximum zero when there are no such pairs and inputs: (7)✦ For a family containing exactly one predicate and either Boolean value , (8)✦ The ordinary tower profile is the side sensitivity (6) of the level family: (9)✦ The joint tower profile of the predicate family at level is its joint sensitivity for the Boolean value , as defined in (7): (10)✦
In the paper, the result reads: for , is the maximum sensitivity of over indices and inputs with ; is the maximum number of raw coordinates whose single flip changes both and from to , over fixed pairs and common inputs where both equal ; empty maxima are zero, and both final joint profiles vanish when .
What Is Checked
The definitions and the singleton identity (8) are stated over finite coordinate sets and arbitrary predicate families of the indicated size; the tower profiles (9) and (10) use a labelled tournament, arbitrary base families, and nonnegative heights and levels.