Constructs total Boolean functions with block sensitivity \mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha for a fixed α > 2, disproving the quadratic strengthening of the Sensitivity Conjecture. Here s(f) counts influential individual-bit flips, while block sensitivity allows disjoint groups of bits to change together. (Lean)
Manuscript
A superquadratic separation between sensitivity and block sensitivity
September 25, 2026 · source · Lean formalization available · cite as \cite{OAI:A-superquadratic-separation-between-sensitivity-and-block-sensitivity-September-25-2026}
We disprove the quadratic strengthening of the Sensitivity Conjecture by constructing nonconstant total Boolean functions whose block sensitivity grows faster than any constant multiple of sensitivity squared. In fact, for some fixed α > 2, our examples have unbounded block sensitivity and satisfy \mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha.
Result 132 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md