{"id":"openai-math/Average-Sensitivity-of-Polynomial-Threshold-Functions","pdf":"https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026","tags":["boolean-functions","complexity-theory","threshold-functions"],"score":0,"title":"Average sensitivity of polynomial threshold functions","domain":"Theoretical computer science","family":"127","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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`$.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-25","reactions":{},"formalized":true,"family_title":"Average sensitivity of polynomial threshold functions"}