Short··0:21·Theoretical computer science
Sensitivity Conjecture: OpenAI Claims a Superquadratic Gap
Watch on YouTubeAbout the problem →
About this video
Sensitivity counts how many single bit flips change a Boolean function's output; block sensitivity counts how many separate groups of bits can each change it. Huang proved the Sensitivity Conjecture in 2019, giving block sensitivity at most sensitivity to the fourth power, and the best examples had block sensitivity about sensitivity squared, so many expected the square to be the truth. OpenAI claims functions whose block sensitivity grows faster than any constant times sensitivity squared, bs(f) ≥ s(f)^α for a fixed α greater than 2; this is OpenAI's preprint, not yet peer reviewed. The coins show Rubinstein's 1995 example on 36 bits, with sensitivity 6 and block sensitivity 18.
Paper (OpenAI, catalogue result 132):
- A superquadratic separation between sensitivity and block sensitivity: github.com/openai/math/blob/main/preprints/A-superquadratic-s…
The animation illustrates the result; it is not a proof.
Gradient Damage: mathematics you can see, equations you can hear.
youtube.com/@gradientdamage
Every result explained: gradientdamage.com/p/132
About the problem
Theoretical computer science·OpenAI Math·Result 132
A superquadratic separation of sensitivity and block sensitivity
Constructs total Boolean functions with block sensitivity bs (f) ≥ s(f)α 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. (Lean)
Topics
sensitivity conjectureblock sensitivitysensitivity vs block sensitivityBoolean functionsHuang sensitivity theoremHao HuangRubinstein functionquery complexitydecision tree complexitycomplexity theorytheoretical computer sciencehypercubesuperquadratic separationOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicscomputer sciencemath shorts3D animation
