Published: March 15, 2011
Abstract: [Plain Text Version]
The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. Answering a question by O'Donnell, we show that every Boolean function represented by a $k$-CNF (or a $k$-DNF) has average sensitivity at most $k$. This bound is tight since the parity function on $k$ variables has average sensitivity $k$.