Browse › Theoretical computer science › 127 Average sensitivity of polynomial threshold functions
Average sensitivity of polynomial threshold functions
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
For every n ≥ 1 and $1\le d\le n$, we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most $8d\sqrt n$. This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention $\mathop{\mathrm{sgn}}\nolimits (0)=1$.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI math release, Lean scope notes for family 127: Average sensitivity of polynomial threshold functions (lean/docs/127.md, 2026-10-06). The release's own scope note says the formalization proves the bound $8d\sqrt n$ with $\mathrm{sgn}(0)=1$ (the asymptotic bound, not the exact-extremizer conjecture), and links the comparator statement
ComparatorChallenges/GotsmanLinial.lean. [AI-generated per source] - OpenAI math release, Lean file
OAI/Combinatorics/GotsmanLinial/Main.lean(github.com/openai/math, commit adc7f12, October 2026). The theoremgotsmanLinialStatementconcludesaverageSensitivity (polynomialThreshold p) ≤ 8 * d * Real.sqrt nfor $1\le d\le n$, i.e. the paper's Theorem 1.1.
Possibly relevant literature (found by the agent, not checked)
- Cristopher Moore and Alexander Russell, Heat and Noise on Cubes and Spheres: The Sensitivity of Randomly Rotated Polynomial Threshold Functions (arXiv:1408.5425, August 2014). Its abstract says it proves an average-case version of the Gotsman–Linial conjecture for randomly rotated PTFs restricted to the cube, an earlier partial result toward the $O(d\sqrt n)$ bound not cited in the paper's introduction.
Digests and expositions
- Open Mathematics Courses / Claude Opus 5.5, Average sensitivity of threshold functions (Open Mathematics Courses, undated). Three lessons explain the paper's one-sided coupling inequality, weighted grading, anticommutator edge count, and noise-sensitivity consequence, with exercises and a statement that independent review is incomplete. [AI-generated per source]
- Gist.Science, A compensated coupling bound for the average sensitivity of polynomial threshold functions (summary of Research Square rs-11323154, 2026-10-13). This AI-generated synopsis attributes a refinement of OpenAI's coupling argument to Prathmesh Lagdive, Vaibhav Aglave, and Suraj Damre; the linked original manuscript could not be accessed during collection. [AI-generated per source]
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 127
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026,
author = {{OpenAI}},
title = {{Average sensitivity of polynomial threshold functions}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf}{OAI:Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/127.md. The Lean statements have not been checked by people against the paper's claims.
Family 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\sqrt n$, uniformly for $1\le d\le n$. Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with $\mathop{\mathrm{sign}}\nolimits (0)=1$.
This is the only paper in this family.