Short··0:20·Theoretical computer science
Gotsman–Linial Conjecture: OpenAI Claims Sensitivity ≤ 8d√n
Watch on YouTubeAbout the problem →
About this video
Cut the n-dimensional Boolean cube with the sign of a degree-d polynomial: how many of the n one-bit flips change the answer, on average? Gotsman and Linial conjectured in 1994 that low-degree polynomial threshold functions can only be sensitive to about d√n bits, far fewer than parity's n. OpenAI claims a proof that the average sensitivity is at most 8d√n for every n ≥ 1 and 1 ≤ d ≤ n, the asymptotic form of the Gotsman–Linial conjecture; this is OpenAI's preprint, not yet peer reviewed. The cube shown is the real 8-cube with real polynomials, and every flip count shown is computed exactly.
Paper (OpenAI, catalogue result 127):
- Average sensitivity of polynomial threshold functions: github.com/openai/math/blob/main/preprints/Average-Sensitivit…
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/127
About the problem
Theoretical computer science·OpenAI Math·Result 127
Average sensitivity of polynomial threshold functions
Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most 8d√n, uniformly for 1 ≤ d ≤ n. Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with sign (0)=1. (Lean)
Topics
Gotsman-Linial conjectureaverage sensitivitypolynomial threshold functionsPTFBoolean functionsBoolean cubehypercubeanalysis of Boolean functionssensitivitytotal influenceparity functionthreshold functionstheoretical computer sciencecomplexity theorylearning theoryOpenAIOpenAI mathAI mathematicsAI proofmathsmathematicsmath shorts3D animation
