A superquadratic separation of sensitivity and block sensitivity

What OpenAI claims

Constructs total Boolean functions with block sensitivity bs (f) ≥ s(f)^α 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)

Paper

1. A superquadratic separation between sensitivity and block sensitivity

   25 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract 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 bs (f) ≥ s(f)^α.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.