Family 132Theoretical computer scienceLeanNot yet digestedfeatured

A superquadratic separation of sensitivity and block sensitivity

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.

Manuscripts in this family · 1

A superquadratic separation between sensitivity and block sensitivity

Sep 25, 2026·paper.pdfLean

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

Full abstract

PDF on GitHub LaTeX source