The Setting
A recursive Boolean family has sensitive coordinates at each output value, and two predicates can share sensitive coordinates at a common input. The ordinary and joint profiles measure these two kinds of sensitivity through the recursion.
Let be a finite coordinate set and let . Write , with . A tournament on a finite vertex set is a directed graph with no loops and exactly one directed edge between each pair of distinct vertices.โฆ Write for an edge of . A tournament with natural parameter is regular if it has vertices, each with exactly outgoing neighbors.โฆ
A good labeling of , where , is a map satisfying (1) for every with and every assignment : (1)โฆ
Sensitivity Profiles
The block flip of an input in a block is the input defined by (2), where complements a Boolean value: (2)โฆ
The local sensitivity of a Boolean function at an input is the number of coordinates whose flip changes its value.โฆ The local joint sensitivity of Boolean functions at an input is the number of coordinates whose flip changes both values, as in (3): (3)
For a family of Boolean predicates on and , the side sensitivity and joint sensitivity are the maxima in (4); an empty eligible set has maximum zero: (4)
A nested family of Boolean predicates on is a family whose acceptance sets decrease with the predicate index, as specified in (5) for every input : (5)โฆ
The Recursive Family
Let have predicates. For an input , its child input at row and label is , defined by .โฆ The reversed gate index at predicate position is .โฆ
For a family of Boolean predicates on , a predicate index and a vertex , the row clause is the Boolean predicate on that requires acceptance by the last predicate throughout row and rejection by the gate predicate at each labeled outgoing neighbor, as in (6): (6)โฆ
For a family of Boolean predicates on , the recursive family is the family of Boolean predicates on that accept when at least one row clause accepts, as in (7): (7)โฆ
Iteration
A base collection is a collection whose entry is a family of Boolean predicates on for each . For each nonnegative integer level and each nonnegative integer , the tower coordinate set and iterated family are defined by (8), using the fixed tournament and labeling: (8)
For a natural number , the ordinary tower profile and joint tower profile are the side and joint sensitivities in (9), with subtraction truncated at zero: (9)
The Claim
Theorem 1. Let be a regular tournament with parameter and let be a good labeling by labels. Let be a nested family of Boolean predicates on a finite coordinate set. Its recursive family satisfies (10): (10)โฆ For a base collection with nested and an integer depth , the tower profiles satisfy (11): (11)โฆ
In the paper, the result reads: for and , fix the regular tournament and labeling of Sectionย 2, take and , and for write and ; the four bounds are (12): (12)
What Is Checked
The recursive statement concerns nested Boolean families on finite coordinate sets, regular tournaments and good labelings; the tower statement concerns a base collection whose -predicate family is nested, at depths below .