Family 127Theoretical computer scienceLeanNot yet digested
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 , uniformly for . Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with .
Manuscripts in this family · 1
Average sensitivity of polynomial threshold functions
Sep 25, 2026·main.pdfLean
For every n ≥ 1 and , we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most . This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention .