{"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":2,"published":"2026-09-25","reactions":{},"discussion":[{"url":"https://x.com/RobinKothari/status/2110829273108127765","date":"2026-10-15","kind":"x","added":"2026-11-03","author":"Robin Kothari","handle":"RobinKothari"},{"url":"https://x.com/RobinKothari/status/2111231171371712667","date":"2026-10-16","kind":"x","added":"2026-11-03","author":"Robin Kothari","handle":"RobinKothari"}],"formalized":true,"family_title":"A superquadratic separation of sensitivity and block sensitivity"}