A superquadratic separation of sensitivity and block sensitivity
OpenAI research collection · 1 manuscript · Source checked 2026-10-19
OpenAI's result summary
Constructs total Boolean functions with block sensitivity \mathop{bs}\nolimits (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.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
A superquadratic separation between sensitivity and block sensitivity
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{bs}\nolimits (f)≥…
Full source 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 \mathop{bs}\nolimits (f)≥ s(f)^α.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.