For and , let be the vertex obtained from by reversing coordinate . The average sensitivity of a function on is . It is also called the total influence of . Throughout, for and for . A real polynomial is multilinear when no variable appears in it with an exponent larger than one. On the cube, the identities turn every real polynomial into a multilinear polynomial of no larger degree with the same values. A polynomial threshold function of degree at most is a function on , where is a real multilinear polynomial of degree at most . The question is how large the average sensitivity of a polynomial threshold function can be, in terms of its degree and the dimension .
The levels of the cube are the sets of vertices on which takes a fixed value. Gotsman and Linial proposed that, among polynomial threshold functions of degree in variables, the average sensitivity is largest for the sign of a degree- polynomial in whose roots lie between levels of the cube. Chapman constructed counterexamples to this exact assertion. He distinguished it from the asymptotic form of the conjecture of Gotsman and Linial. Kim, Maldonado, and Wellens independently constructed quadratic counterexamples for odd . The classical symmetric examples are the signs of suitable degree- polynomials in . For they have average sensitivity of order . For , Harsha, Klivans, and Meka proved that every polynomial threshold function of degree at most on satisfies . In independent work, Diakonikolas, Raghavendra, Servedio, and Tan proved . Kane then reached the square-root exponent in the dimension, proving for .
The preprint proves that for integers and , every polynomial threshold function of degree at most on satisfies . This bound establishes the asymptotic form of the conjecture of Gotsman and Linial with an absolute constant. From it the preprint derives a dimension-free noise sensitivity bound and an agnostic learning guarantee, neither of which the Lean library contains.
The Lean library GotsmanLinial proves for every real multilinear polynomial in variables of degree at most , for all natural numbers and , without the preprint’s restriction to and . Lean has checked every result of the Lean library, so the Lean library is the reference: the results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only: it gives the results their order and their names. The Lean library takes no result as a hypothesis.
GotsmanLinial is a Lean library: 13 items, in five groups. Each has a page written by OctoInform, listed below.
No item matches.