Boolean Functions Break Every Quadratic Bound on Block Sensitivity

Sensitivity counts the individual bits whose flips change a Boolean function’s output at a given input. Block sensitivity counts disjoint groups of bits that can each change the output when flipped as a group. A function can therefore be insensitive to every single-bit flip at an input while remaining sensitive to several larger, disjoint changes.

For the four-bit illustration, let f(x) = (x₁ ∧ x₂) ∨ (x₃ ∧ x₄). At 0000, no single-bit flip changes the output, but flipping either pair makes the output 1. The local sensitivity is 0 and the local block sensitivity is 2. These are local counts: global sensitivity and block sensitivity are each maximized over all inputs, and the two maxima may occur at different inputs.

The main result is that for every positive constant C, there is a nonconstant total Boolean function f such that:

bs(f) > C s(f)²

“Total” means the function is defined on every bit string. The result rules out a universal quadratic bound, while remaining compatible with a fourth-power upper bound.

The construction begins with well-separated bit strings, called centers. For each center, a test accepts inputs within an integer radius, measured by the number of differing bits. Successively smaller radii give nested tests: every input accepted by a smaller-radius test is also accepted by a larger-radius one.

Nesting controls how many tests a single bit flip can change. A one-bit flip changes the distance to the nearest center by at most one, so it cannot cross two distinct integer thresholds at once. In the twelve-bit illustration, the distance moves from two to one and exactly one test changes. The initial joint sensitivity is zero. Joint sensitivity counts bits that change a fixed pair of tests together at the same input. The tests are nested, but they are not necessarily monotone in the input bits.

The next step builds larger tests from disjoint copies of these child inputs, arranged in rows. Between every pair of rows, the construction chooses one arrow direction. Each row has exactly M² outgoing arrows, and each arrow selects a position in its destination row. A clause for a row requires every child in that row to pass the strongest test, while each outgoing arrow requires its selected child in the destination row to fail a weaker test. The parent accepts if any clause holds. Changing the weaker test generates the next nested family.

Within a clause, each condition depends on a different child, so one raw bit can affect at most one condition. Across rows, the construction also uses disjoint coordinates.

At the all-zero input, the construction turns old sensitive blocks into a larger collection. Take an old sensitive block and copy it into every child of one row; flipping the union makes all targets in that row true. The other rows remain zero, so the outgoing gates still pass and the parent accepts.

Each old block produces a new block for each row. The blocks remain disjoint within a row and across rows. With k = 2M² + 1 rows, the number of sensitive blocks is multiplied by k at each level. Starting with M blocks, the level-ℓ count is M k^ℓ.

This gives growing block sensitivity at a particular input. The harder constraint is keeping ordinary sensitivity small at every input, including inputs where the parent rejects.

Consider an arbitrary input where the parent rejects. For a one-bit flip to repair a clause, that clause must fail exactly one condition. Focus on clauses whose targets all pass and whose only failure is a gate. If there is an arrow from row i to row j, row j’s strongest test passing means the selected child also passes the weaker test. That makes the gate on the arrow fail for row i.

Among the candidate rows under consideration, each row can therefore have at most one outgoing arrow. If there are m such rows, there are m(m−1)/2 arrows between them, while the limit of one outgoing arrow per row allows at most m. Thus m ≤ 3: four rows require six arrows but can accommodate only four.

A gate repair generally requires the same child to change both the weaker test and the strongest test. For all but at most one candidate row, those two changes must occur together through the same raw bit. That is why the estimates track joint sensitivity as well as ordinary sensitivity. Joint sensitivity begins at zero, though it need not remain zero as the construction is repeated; the estimates explicitly allow for the exceptional row.

A separate labeling argument uses a union bound to show that suitable labels exist that prevent sixteen target-repair candidates from coexisting. The label-existence calculation and the full recurrence algebra are not developed here; the construction relies on their existence. Four coupled estimates track ordinary and joint sensitivity for both output values. Choosing the size parameter sufficiently large controls the accumulated joint-sensitivity contribution.

After depth d, the construction takes the OR of M disjoint copies to balance the two output cases. At a rejecting input, sensitive bits may come from any copy. At an accepting input, they can matter only when exactly one copy accepts. The resulting bounds are:

s(f) ≤ 2(d+2)M^(d+1), bs(f, 0) ≥ M²(2M²+1)^d

Dividing the block-sensitivity lower bound by the square of the sensitivity upper bound gives:

bs(f) / s(f)² ≥ 2^d / (4(d+2)²)

This grows without bound as d increases. Choose the depth first, then M and admissible labels, and any proposed quadratic constant is exceeded.

The result also yields a fixed exponent greater than two. At depth 9, the construction gives fixed bounds A = 22M^10 and B = M²k^9, with B/A² ≥ 128/121 > 1. Repeatedly composing disjoint copies of this seed keeps sensitivity at most A^m, while block sensitivity at zero is at least B^m. Because the seed outputs zero at zero, its disjoint sensitive blocks multiply through composition.

Set α = log(B)/log(A). Since B > A², α > 2. The composed functions have block sensitivity at least sensitivity to this fixed power, and their block sensitivity grows without bound.