Average sensitivity of polynomial threshold functions
For every integer and , if is a real multilinear polynomial of degree at most and is defined by with , then the average sensitivity of under the uniform law satisfies .
Every step in the proof of Theorem 1—perturbation, parity transformation, block-vanishing, coupling construction, and application of Lemmas 2 and 3—is complete and mathematically rigorous.
“Theorem 1. Let n ≥ 1 and 1 ≤ d ≤ n be integers. Let p be a real multilinear polynomial of degree at most d, and define f : {−1, 1}n → {−1, 1} by f(x) = sgn(p(x)), with sgn(0) = 1. Then, for average sensitivity under the uniform law, I(f) ≤ 8d√n.” · Show in paper