Block sensitivity versus spectral sensitivity of Boolean functions
Follow the latest progress by email.
Can block sensitivity of a total Boolean function be bounded by a constant times the square of its spectral sensitivity? A quartic general upper bound was known, leaving the possible quadratic improvement open.
Why it matters and what counts as progress
Why it matters: A superquadratic separation limits how spectral sensitivity controls the query complexity measured by block sensitivity.
What counts as progress: Construct a superquadratic separation or improve the general upper exponent with a matching lower bound.
How the problem developed
Huang Proved the sensitivity conjecture, establishing that Boolean-function degree is at most the square of sensitivity; this did not settle the analogous block-sensitivity versus spectral-sensitivity question.
Aaronson, Ben-David, Kothari, Rao, and Tal Introduced spectral sensitivity and asked whether block sensitivity is bounded by a constant times its square.
- 1 Aug 2026 · Counterexample [3]
Alexander Meiburg Constructed Boolean functions with block sensitivity growing faster than the square of spectral sensitivity, with exponent 2.127 in the reported family.
AI contribution
Block Sensitivity can exceed Spectral Sensitivity Squared
Meiburg constructs a total Boolean function on 2,017,584 variables with block sensitivity at least 14,011 and spectral sensitivity at most 89.0162. Composition yields an exponent of at least 2.127, refuting a proposed quadratic upper bound.
Sources
Website timeline
Publication dates and editorial changes.
AI-origin construction gives a superquadratic sensitivity separation