Episode 132, October 2026

Beats sensitivity squared?

A claimed superquadratic gap between sensitivity and block sensitivity, against the quadratic form of the Sensitivity Conjecture

Covers result 132 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 132: Beats sensitivity squared? A four by four grid of zero bits with eight disjoint pairs outlined.

6:26. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Take a Boolean function of n bits. Its sensitivity at an input counts the single bits whose flip changes the answer; block sensitivity counts how many disjoint blocks of bits can each, flipped on its own, change it. Both are maximized over inputs, and block sensitivity is always at least sensitivity. In Rubinstein’s example on 16 bits, four rows of four, the function is 1 when some row reads exactly 1100 or 0011: at the all-zero input no single flip matters, but eight disjoint pairs do, while no input has sensitivity above 4.

Nisan introduced block sensitivity in 1989, and the Sensitivity Conjecture asked whether it is bounded by a polynomial in sensitivity. Nisan and Szegedy suggested the bound might be sensitivity squared. Rubinstein’s family reaches half of sensitivity squared, Virza improved it slightly, and Ambainis and Sun reached two thirds. In 2019 Huang proved the conjecture; with Tal’s bound, block sensitivity is at most sensitivity to the fourth. Whether squared is the truth stayed open.

Result 132 is one OpenAI preprint (11 pages, September 25, 2026). It claims that no constant C gives bs(f) ≤ C·s(f)² for all nonconstant total Boolean functions: for every depth d ≥ 1 it builds a function with bs(f)/s(f)² ≥ 2^d/(4(d + 2)²), which grows without bound. Composing a fixed example with itself gives a fixed exponent α above 2 and an unbounded family with bs(F_m, 0) ≥ s(F_m)^α.

What it doesn’t claim

The functions are enormous. The guaranteed ratio first passes 1 at depth 9, where the paper takes M ≥ 9¹⁰ (about 3.5 billion) and the function has more than 10²³⁷ input bits; with the smallest allowed M, the exponent is about 2.00025. The paper claims some fixed exponent above 2, not a particular one, and it does not touch Huang’s upper bound of 4. The construction adapts an August 2026 preprint by Alexander Meiburg showing that block sensitivity can exceed spectral sensitivity squared, a weaker statement since spectral sensitivity is at most sensitivity; according to the paper, Meiburg credits GPT-5.6-Sol with its gated tournament ideas.

Where it stands

Posted as a preprint: OpenAI, 11 pages, dated September 25, 2026
Peer reviewed: Not yet
Checked in Lean: The quantitative bound, the unbounded ratio and the fixed exponent. We have not run the check

Last checked October 19, 2026. The preprint has not been revised. OpenAI published a Lean formalization of the quantitative bound, the unbounded ratio and the fixed exponent (comparator statement; 51 files and 4,387 lines with its imports, not counting Mathlib, with no unproved steps that we could find). We have not run the check. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

The base. Place M centres in the cube, each the indicator of its own block of L = d + 2 bits, so any two differ in 2L bits. The base predicates accept inputs within distance d, d − 1, …, 0 of some centre: nested Hamming balls. One flip moves the distance by at most one, so no flip switches two of them at once. From the all-zero input, flipping one centre’s block lands on that centre: M disjoint blocks.
The recursion. Each new level splits its input into k = 2M² + 1 rows of r = ⌈√M⌉ children. A tournament orients every pair of rows, each row with M² outgoing edges, and every edge carries a label: a position in the row it points to. Clause i asks every child in row i to pass the strongest child predicate (targets) and, for each edge i → j, the labelled child of row j to fail a weaker one (gates). The parent accepts when some clause holds. Flipping copies of one child block across a whole row satisfies that row’s clause at zero, so the number of blocks multiplies by k each level.
Sensitivity stays small. A flipped bit lies in one child, so at a rejecting input only clauses failing exactly one condition can switch on. Among those failing one target, an edge between two of them forces its label, and labels fixed by a random-choice argument rule out sixteen such rows. Among those failing one gate, each has at most one outgoing edge inside the set, so there are at most three, and repairing all but one of them needs one bit to switch two child predicates together. Tracking that joint sensitivity gives four coupled recurrences.
Counting up, then composing. With M ≥ 9^d+1, sensitivity grows by about a factor M per level while blocks grow by k. An OR of M copies evens out the sensitivity at rejecting and accepting inputs: s(f) ≤ 2L·M^d+1 and bs(f, 0) ≥ M²k^d, so the ratio is at least 2^d/(4L²). Composition multiplies sensitivity at most and block sensitivity at zero at least, so a seed that is zero at zero with bs(f, 0) above s(f)², repeated, gives α = log B / log A above 2.

The numbers in the video

Rubinstein’s 16-bit example: sensitivity 4 over all 65,536 inputs; block sensitivity 8 at the all-zero input.
The base family, exactly on nine small cases: S_0,0 = d + 1, S_0,1 = LM, no joint sensitivity.
The construction at depths 1 and 2 with M = 3 (up to 17,328 bits per predicate), far too small for the theorem itself: random labels pass the label property on all 969 sixteen-row sets; all 1,083 depth-2 blocks switch every predicate on at zero; every sensitivity a local search found stays within the recurrences, meeting them on the accepting side at the first level (51 of 51, 24 of 24).
Composition: both inequalities held on 56 random pairs of small functions.
Depth 9 with M = 9¹⁰: about 3.5 × 10²³⁷ input bits, ratio bound 512/484 ≈ 1.058, exponent ≈ 2.00025.

Read the source

A superquadratic separation between sensitivity and block sensitivity (PDF), 11 pages.
The Lean scope note.
The collection’s catalog, where this is result 132.

The paper

OpenAI groups related papers into one result; this one has a single paper.

A superquadratic separation between sensitivity and block sensitivity

Transcript

Read the full script

0:00Sensitivity and block sensitivity

Take a Boolean function of n bits. Its sensitivity at an input counts the single bits whose flip changes the answer, and the sensitivity of the function is the largest such count. Block sensitivity allows groups instead: how many disjoint blocks of bits can each, flipped on its own, change the answer? Here is Rubinstein’s example on 16 bits, in four rows of four. The function is one when some row reads exactly 1100, or 0011. At the all-zero input no single flip changes anything, but eight disjoint pairs do, so the block sensitivity is eight. In our check, no input had sensitivity above four. Nisan introduced block sensitivity in 1989, and the Sensitivity Conjecture asked whether it is bounded by a polynomial in sensitivity. Nisan and Szegedy suggested the bound might be sensitivity squared. Rubinstein’s family reaches half of sensitivity squared; Virza improved it slightly, and Ambainis and Sun reached two thirds. In 2019 Huang proved the conjecture, and with Tal’s bound, block sensitivity is at most sensitivity to the fourth. Whether squared is the truth stayed open.

1:16The claim

Result 132 is a single OpenAI preprint, 11 pages, dated September 25. It claims that no constant times sensitivity squared bounds block sensitivity. For every depth d ≥ 1, it builds a nonconstant function whose block sensitivity divided by sensitivity squared is at least 2^d / (4(d + 2)²). That grows without bound. Composing one fixed example with itself then gives a fixed exponent alpha, greater than two, and an unbounded family with block sensitivity at least sensitivity to the alpha. These functions are enormous. The guaranteed ratio first passes one at depth nine, where the paper takes a size parameter M of at least 9¹⁰, about 3.5 billion, and the function has more than 10²³⁷ input bits. With the smallest allowed M, alpha is about 2.00025, just above two. The construction adapts an August 2026 preprint by Alexander Meiburg showing that block sensitivity can exceed spectral sensitivity squared, a weaker statement; according to the paper, Meiburg credits GPT-5.6-Sol with its gated tournament ideas. OpenAI published a Lean formalization of all three statements: 51 files and about 4,400 lines, not counting Mathlib. We have not run the Lean check.

2:47How the proof goes

The construction is recursive and starts small. Place M far-apart centres in the cube, each the indicator of its own block of d + 2 bits. The base predicates accept inputs within distance d of some centre, then d − 1, down to zero: nested Hamming balls. One flip moves the distance by at most one, so no flip changes two of these predicates at once. From the all-zero input, flipping one centre’s block lands exactly on that centre, giving M disjoint blocks. At each new level, the input splits into k rows of r children, with k equal to 2M² + 1 and r about √M. A tournament orients every pair of rows, giving each row M² outgoing edges, and every edge carries a label: one position in the row it points to. Clause i asks every child in row i to pass the strongest child predicate, and for each edge from i, the labelled child to fail a weaker one. The parent accepts when some clause holds. At zero, flipping copies of one child block across a whole row satisfies that row’s clause, because its gates sit in other rows, so the number of blocks multiplies by k at every level. The hard part is keeping sensitivity small. A flipped bit lies in one child, so it can repair only one condition of a clause. Take a rejecting input and the clauses that fail exactly one condition. If two of them each fail one target, and one points to the other, the label on that edge is forced, and the labels can be fixed, by a random-choice argument, so that no 16 rows ever line up this way. If they each fail one gate, each has at most one outgoing edge among them, so there are at most three. Repairing all but one of those needs one bit to flip two child predicates together, so the proof tracks that joint sensitivity as well. In our check, we built depths one and two with M equal to three, more than 17,000 bits per predicate, a size far too small for the theorem itself. All 1,083 blocks worked, and every sensitivity our search found stayed within the paper’s recurrences. With M at least 9^(d+1), sensitivity grows by about a factor M per level while the blocks grow by k, about 2M². An OR of M disjoint copies evens out the sensitivity at rejecting and accepting inputs, giving sensitivity at most 2L·M^(d+1), and block sensitivity at zero at least M²·k^d. The ratio is at least 2^d / (4L²). For the fixed exponent, composing functions multiplies sensitivity at most and block sensitivity at zero at least, so a seed that is zero at the all-zero input, with block sensitivity there above its sensitivity squared, repeated, gives alpha above two. In our check, both composition inequalities held on 56 random pairs of small functions.

5:47Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the quantitative bound, the unbounded ratio and the fixed exponent; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the quadratic strengthening of the Sensitivity Conjecture is false: block sensitivity can beat any constant times sensitivity squared, and even a fixed power above two. The true exponent now lies somewhere between just above two and the four from Huang’s theorem.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.