Sensitivity versus block sensitivity: beyond every quadratic bound

← All digests

Family 132 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

A Boolean function makes a yes/no decision from a string of bits. At a given input, some individual bits may be decisive: reversing one changes the answer. Other changes may require coordinated groups of bits.

Sensitivity counts the decisive individual bits. Block sensitivity counts how many disjoint groups can each change the answer when flipped together. Disjointness prevents counting the same decisive information repeatedly.

For decades, researchers asked whether these two measures are always polynomially related for total Boolean functions. Huang answered that question affirmatively in 2019. A sharper possibility remained: perhaps block sensitivity is always at most a universal constant times sensitivity squared.

This manuscript claims to rule out every such quadratic bound. It constructs total Boolean functions with block sensitivity exceeding sensitivity to some fixed power strictly greater than two. This refines the quantitative frontier after Huang’s theorem; it does not disprove the original Sensitivity Conjecture that Huang resolved.

2. Background and essential definitions

Let $f:\{0,1\}^n\to\{0,1\}$. “Total” means that $f$ is defined on every binary input, with no promise restricting which inputs are legal.

For $B\subseteq\{1,\ldots,n\}$, write $x^B$ for the input obtained by flipping exactly the bits in $B$. The sensitivity at $x$ is

$$s(f,x)=\bigl|\{i:f(x^{\{i\}})\ne f(x)\}\bigr|, \qquad s(f)=\max_x s(f,x).$$

Block sensitivity $\operatorname{bs}(f,x)$ is the maximum number of pairwise disjoint nonempty sets $B_1,\ldots,B_m$ for which each $f(x^{B_j})\ne f(x)$. Then

$$\operatorname{bs}(f)=\max_x\operatorname{bs}(f,x).$$

Each singleton sensitive coordinate is also a sensitive block, so $s(f)\le\operatorname{bs}(f)$. Both measures take maxima over inputs. They differ from average sensitivity, which averages over an input distribution and is the subject of family 127.

A simple pointwise example helps. Partition the input into pairs and let $f$ accept if at least one pair consists of two ones. At the all-zero input, flipping any one bit changes nothing, but flipping both bits of any pair makes the function accept. Thus pointwise block sensitivity can greatly exceed pointwise sensitivity. However, other inputs can have much larger sensitivity, so this example alone does not give the desired separation between the global maxima.

That is the central difficulty: constructing many disjoint sensitive blocks at one input while controlling individual-bit sensitivity at every input.

3. Development history and previous partial results

Nisan introduced block sensitivity in the study of parallel computation and decision trees. Nisan and Szegedy’s 1994 polynomial-degree analysis connected these measures to algebraic representations of Boolean functions and explicitly suggested a quadratic inequality.

Rubinstein gave a quadratic separation, showing that any universal polynomial upper bound would need exponent at least two. Later examples improved constants and lower-order terms. Virza obtained $\operatorname{bs}(f)=\tfrac12s(f)^2+\tfrac12s(f)$, while Ambainis and Sun reached $\tfrac23s(f)^2-\tfrac13s(f)$.

These examples demonstrated a substantial gap, but they still fit beneath some constant multiple of $s(f)^2$. Improving a coefficient below one does not establish an exponent above two.

Huang’s 2019 Sensitivity Theorem, combined with degree–block-sensitivity comparisons, gives the universal quartic bound $\operatorname{bs}(f)\le s(f)^4$. Subsequent work sharpened its leading constant. The original polynomial relationship was therefore settled, while the best possible exponent remained between the known quadratic constructions and the quartic upper bound.

The immediate structural predecessor cited by this manuscript is Meiburg’s 2026 spectral-sensitivity construction. Spectral sensitivity measures the operator norm of the graph joining inputs where one bit changes the answer. It is at most ordinary sensitivity. Therefore a separation from its square does not automatically give a separation from ordinary sensitivity squared, the larger denominator relevant here.

The new construction adapts the tournament-based organization of that work but adds direct control of ordinary sensitivity and simultaneous changes of nested predicates. The amplification by composition has precedents in Tal’s work and in earlier observations about how a sufficiently strong seed could yield a power separation.

4. What the new manuscripts claim

For every real constant $C>0$, the manuscript states that there is a nonconstant total Boolean function $f$ with

$$\operatorname{bs}(f)>C\,s(f)^2.$$

More concretely, for each integer construction depth $d\ge1$, it gives a function satisfying

$$\frac{\operatorname{bs}(f)}{s(f)^2} \ge\frac{2^d}{4(d+2)^2}.$$

The right side grows without bound. Here $d$ is a construction parameter, not the algebraic degree of the function.

The paper then fixes one sufficiently strong finite seed and composes it repeatedly. It claims the existence of an absolute real $\alpha>2$ and total Boolean functions $F_m$ such that

$$\operatorname{bs}(F_m,0)\ge s(F_m)^\alpha, \qquad \operatorname{bs}(F_m,0)\longrightarrow\infty.$$

The zero denotes the all-zero input. This is stronger than an unbounded ratio produced only by varying exponents: one fixed exponent above two works across the resulting infinite sequence.

The construction uses a large fixed seed. In the manuscript’s explicit choice, bounds $s(f)\le A$ and $\operatorname{bs}(f,0)\ge B$ satisfy $B/A^2\ge128/121>1$. It sets $\alpha=\log B/\log A$. This establishes a strict separation above two, not a claim that the optimal exponent is now known or close to four.

5. Why the advance matters

Provisional importance: 3/5. The claim would settle a natural quantitative strengthening of one of Boolean complexity’s best-known conjectures. It would show that coordinated changes can outgrow every quadratic function of the worst-case number of individually decisive bits.

The distinction is conceptually valuable because many complexity measures are polynomially related without being quantitatively interchangeable. Once a polynomial relation is known, determining its sharp exponent can reveal mechanisms hidden by the broad classification.

The construction also demonstrates why pointwise examples are insufficient. The hard part is controlling all inputs, including those where many candidate accepting patterns nearly occur. Tracking additional joint sensitivities supplies information that ordinary sensitivity alone loses under recursion.

The score reflects a substantial contribution to structural complexity. It does not change Huang’s polynomial upper bound or imply an algorithmic separation such as $\mathrm P\ne\mathrm{NP}$. The result narrows one quantitative interval within the theory of total Boolean functions.

6. The main idea

Arrange competing accepting conditions by a tournament

A tournament directs exactly one edge between every pair of vertices. Here its vertices index rows of smaller input blocks. A clause associated with one row requires strong acceptance conditions throughout that row, together with selected rejection conditions in rows to which its tournament edges point.

Each edge receives a label choosing a child position in its destination row. A suitable labeling prevents too many clauses from having the same kind of nearly satisfied local configuration. The manuscript obtains such labels through a probabilistic existence argument: the chance of any forbidden pattern is bounded by summing over all possible patterns.

The parent function accepts when at least one clause holds. Tournament orientation makes different potential accepting rows interfere with one another through their gate conditions. That interference is intended to keep the number of one-bit repairs under control.

Track nested predicates and simultaneous changes

Instead of building only one child function, the construction maintains a nested family of predicates. Their accepting sets decrease as the predicate index increases. The nesting concerns the predicates’ sets, not monotonicity in individual input bits.

At a rejecting parent input, a clause that becomes true after one bit flip must previously have failed exactly one condition. It may have failed a target condition in its own row or a gate condition in another row. Counting such possibilities requires more than separate sensitivity bounds for each child predicate.

Some gate repairs must change both a weaker and a stronger child predicate at once. The manuscript therefore tracks joint sensitivity: how many bits simultaneously reverse two specified predicates. The initial predicates are unions of Hamming balls of different radii around separated centers. A Hamming ball consists of inputs within a fixed number of bit changes of its center. One bit cannot cross two distinct radius boundaries at once, making the initial joint sensitivities especially small.

The recursive estimates preserve enough of this extra information that sensitivity grows essentially by a factor $M$ per level, while the number of disjoint sensitive blocks grows by roughly $2M^2$. An OR of disjoint copies balances behavior at accepting and rejecting inputs. The extra factor of approximately two per level eventually beats the remaining depth-dependent losses.

Amplify one finite advantage

For functions on disjoint groups of input bits, composition substitutes a copy of $g$ into every input of $f$. The paper uses

$$s(f\circ g)\le s(f)s(g).$$

When $g(0)=0$, sensitive blocks at zero also compose, giving

$$\operatorname{bs}(f\circ g,0) \ge\operatorname{bs}(f,0)\operatorname{bs}(g,0).$$

Thus a seed with sensitivity at most $A$ and zero-input block sensitivity at least $B>A^2$ yields, after $m$ compositions, sensitivity at most $A^m$ and block sensitivity at least $B^m$. Choosing $\alpha=\log B/\log A$ converts that repeated multiplicative advantage into the fixed power separation.

This final amplification is straightforward once the seed exists. The main construction work lies in creating the seed while retaining a sensitivity bound valid at every input.

7. Scope, limitations, and open questions

The theorem concerns total Boolean functions. Promise problems can have different relationships among sensitivity measures, and the construction is not a statement about average sensitivity under a chosen distribution.

The resulting exponent is strictly greater than two, but the family does not determine the optimal exponent in the universal upper bound. Huang’s quartic bound remains compatible with the construction. Improving either side of the remaining interval is a natural next question.

Large dimensions and parameters are permitted. The construction establishes a mathematical separation; it does not provide a compact practical classifier with a useful robustness profile. Spectral sensitivity and ordinary sensitivity also remain distinct quantities despite their relationship.

Finally, the random-label argument proves that suitable finite labels exist. It is part of the stated construction rather than a claim about how typical arbitrary Boolean functions behave. The digest reports the seed and amplification claims without independently checking their recursive inequalities.

8. Sources and further reading

Nisan–Szegedy formulates the quantitative problem, Rubinstein and Ambainis–Sun give earlier quadratic examples, and Huang settles the original polynomial conjecture. Meiburg’s spectral construction provides the immediate structural antecedent. The manuscript below supplies the ordinary-sensitivity estimates and their superquadratic amplification.

Source manuscripts

• M1. OpenAI, A superquadratic separation between sensitivity and block sensitivity (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.