A superquadratic separation of sensitivity and block sensitivity

Block sensitivity can outgrow any constant times sensitivity squared.

1 paper September 25, 2026 Explained by AI

Sensitivity counts single input bits whose flip changes a function's answer. Block sensitivity counts separate groups of bits whose flip changes it. Since 1994 experts asked whether block sensitivity is at most sensitivity squared. This paper proves (Lean proof listed) that no constant times sensitivity squared is enough. It builds functions where block sensitivity grows like a power of sensitivity above 2.

First step

1994

Nisan and Szegedy, suggested bs(f) ≤ s(f)²

Significance

Major

It refutes the quadratic inequality suggested in 1994, the long-standing guess for the true power.

Trust

Formal proof listed

Field

Theoretical computer science

1 paper

Best known constant c with block sensitivity about c·s² (before this paper)

Year	Who	Value
2011	Virza	0.5
2011	Ambainis and Sun	0.667

Higher is a bigger gap. This paper shows no fixed constant is the limit.

The explanation

Picture 16 light switches in four rows of four, wired to one lamp. The lamp is on when some row shows one of two patterns. Either that row's first two switches are up and its last two down, or the reverse. Start with every switch down. The lamp is off, and flipping any single switch leaves it off. Yet eight separate pairs of switches exist, two in each row. Flipping any one of those pairs turns the lamp on.

Two counts capture this gap. A Boolean function takes a string of 0s and 1s and returns 0 or 1. Here the switches are the input and the lamp is the output. The sensitivity at an input counts the single switches whose flip changes the output. The block sensitivity counts the most non-overlapping groups of switches whose flip changes the output. A function's score on each count is its largest value over all inputs. A single switch is a group of one, so block sensitivity is never smaller. For the lamp, checking all 65,536 settings by computer gives sensitivity 4. Its block sensitivity is at least 8.

Noam Nisan introduced block sensitivity in 1989, in work on parallel computation. The Sensitivity Conjecture asked whether block sensitivity is always at most some fixed power of sensitivity. In 1994, Nisan and Mario Szegedy suggested a sharper guess: block sensitivity is at most sensitivity squared. David Rubinstein's 1995 example showed that the power could not be below two. Madars Virza later found functions with block sensitivity ½s² + ½s, where s is the sensitivity. Andris Ambainis and Xiaoming Sun then reached ⅔s² − ⅓s. At sensitivity 10 that is about 63, still below 100.

In 2019, Hao Huang proved the Sensitivity Conjecture. With earlier work by Avishay Tal, it gives block sensitivity at most s⁴ for every function. Jake Wellens later sharpened this to at most √(2/3)·s⁴ + 1. So the right power sat somewhere from 2 to 4. The open question was whether squared, times some fixed constant, always suffices.

This paper proves that it does not. Pick any constant C, however large. Some function has block sensitivity bigger than C times its sensitivity squaredSource 1. The paper also gives a fixed power α above 2. An endless family of functions has block sensitivity at least s to the power αSource 2. That block sensitivity grows without limit.

The hard part is not making many sensitive groups. It is keeping single-switch sensitivity low at every input, not just at the starting one. The paper builds its functions in levels. Each level arranges smaller copies in rows and links every pair of rows by one one-way arrowSource 3. Randomly chosen labels on the arrows rule out small patterns that would let single flips pile upSource 4. The paper also counts flips that change two linked conditions at onceSource 5. That extra count keeps sensitivity in check as the levels stack. The closest earlier work, by Alexander Meiburg in 2026, used a similar row-and-arrow design. It beat a weaker measure, spectral sensitivity, which is never larger than sensitivity. So his result did not settle this questionSource 6.

Per level, the number of sensitive groups is multiplied by 2M² + 1, where M is a large size setting. Sensitivity grows by only about a factor MSource 7. The ratio of block sensitivity to sensitivity squared is at least 2^d divided by 4(d+2)², for d levelsSource 8. That bound first exceeds 1 at nine levels, where it equals 128/121, about 1.06Source 9. Repeating that nine-level function inside itself then gives the fixed power αSource 10.

These functions are enormous. The paper requires M to be at least 9 to the power d+1Source 11. At nine levels, that makes the input a number of bits with 238 digits. With that smallest allowed setting, my own calculation from the paper's formulas gives α of about 2.00025. The paper itself only states that α is above 2. It does not say where between 2 and 4 the true power lies.

How sure is this? A computer proof checker called Lean has checked formal versions of both results. One is the ratio bound for every number of levels. The other is the fixed power α above 2, measured at the all-zero input. The Lean scope note links a Comparator statement for the separation. No specialist review of the paper has been published.

What it doesn't show. This does not pin down the true power, which known results place somewhere from 2 to 4.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Lean proofs of both main statements are listed. The functions are astronomically large, and the power found is only slightly above 2. No specialist review has been published.

Words used

Boolean function: A rule that takes a string of 0s and 1s and returns 0 or 1.
Total Boolean function: A Boolean function that gives an answer for every possible input string.
Sensitivity: The most single bits, at any one input, whose flip changes the answer.
Block sensitivity: The most non-overlapping groups of bits, at any one input, whose flip changes the answer.
Sensitivity Conjecture: The guess, proved in 2019, that block sensitivity is at most a fixed power of sensitivity.
Spectral sensitivity: A related measure built from a network of input changes; it is never larger than sensitivity.
Lean: A computer program that checks each step of a formal mathematical proof.

The original paper

A superquadratic separation between sensitivity and block sensitivity (PDF, opens in a new tab)
September 25, 2026 Formal proof listed

Lean notes

All quoted lines (11)

For every real $C>0$ , there are a positive integer $n$ and a nonconstant total Boolean function $f:\{0,1\}^n\to\{0,1\}$ such that $\bs(f)>C\,s(f)^2.$
A superquadratic separation between sensitivity and block sensitivity Back to text
There exist a real number $\alpha>2$ and nonconstant total Boolean functions $F_m$ , for integers $m\geq1$ , such that $\bs(F_m,0)\geq s(F_m)^\alpha \qquad\text{for every }m, \qquad \bs(F_m,0)\longrightarrow\infty.$
A superquadratic separation between sensitivity and block sensitivity Back to text
At a recursive step, the input is partitioned into disjoint child inputs arranged in rows, and every pair of rows is given one directed edge.
A superquadratic separation between sensitivity and block sensitivity Back to text
Random labels exclude small local configurations in which many accepting subcubes lie close to the same accepting input.
A superquadratic separation between sensitivity and block sensitivity Back to text
We consequently track the number of bits that reverse a fixed pair of distinct predicates simultaneously, in addition to ordinary sensitivity.
A superquadratic separation between sensitivity and block sensitivity Back to text
Since $\lambda(f)\le s(f)$ , a lower bound on $\bs(f)/\lambda(f)^2$ alone does not supply the ordinary-sensitivity separation in Theorem ….
A superquadratic separation between sensitivity and block sensitivity Back to text
With a size parameter $M$ chosen sufficiently large for each fixed depth, their normalization in Section … bounds sensitivity growth by essentially a factor $M$ per level, while the number of disjoint sensitive blocks grows by $2M^2+1$ .
A superquadratic separation between sensitivity and block sensitivity Back to text
More precisely, for every integer $d\ge1$ the construction below gives a nonconstant total Boolean function $f$ with $\frac{\bs(f)}{s(f)^2}\ge \frac{2^d}{4(d+2)^2}.$
A superquadratic separation between sensitivity and block sensitivity Back to text
Moreover, $\frac{B}{A^2} =\frac{(k/M^2)^9}{484} \geq\frac{2^9}{484} =\frac{128}{121}>1.$
A superquadratic separation between sensitivity and block sensitivity Back to text
Repeated composition of that seed gives a power separation.
A superquadratic separation between sensitivity and block sensitivity Back to text
Suppose that $d\geq 1$ and $M\geq 9^{d+1}$ .
A superquadratic separation between sensitivity and block sensitivity Back to text