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{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha$.
Comments and reviews
No comments yet.
Discussed elsewhere
API
curl /api/v1/records/openai-math/A-superquadratic-separation-between-sensitivity-and-block-sensitivity
curl -X POST /api/v1/records/openai-math/A-superquadratic-separation-between-sensitivity-and-block-sensitivity/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-superquadratic-separation-between-sensitivity-and-block-sensitivity/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?mathoverflow.netPhilip WeissOct 8, 2026
Another striking example is the announced disproof of the quadratic sensitivity conjecture. For a Boolean function $f:\{0,1\}^n\to\{0,1\}$ , fix an input $x$ . Its sensitivity at $x$ counts how many individual bits would change the output if flipped. Its block sensitivity at $x$ is the largest…