{"id":"openai-math/A-superquadratic-separation-between-sensitivity-and-block-sensitivity","pdf":"https://github.com/openai/math/blob/main/preprints/A-superquadratic-separation-between-sensitivity-and-block-sensitivity-September-25-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-superquadratic-separation-between-sensitivity-and-block-sensitivity-September-25-2026","tags":["boolean-functions","complexity-theory","sensitivity"],"score":0,"title":"A superquadratic separation between sensitivity and block sensitivity","domain":"Theoretical computer science","family":"132","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":1,"published":"2026-09-25","reactions":{},"discussion":[{"url":"https://mathoverflow.net/a/515856","date":"2026-10-08","kind":"web","site":"mathoverflow.net","text":"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…","added":"2026-10-24","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Philip Weiss"}],"formalized":true,"family_title":"A superquadratic separation of sensitivity and block sensitivity"}