Volume 7 (2011) Article 4 pp. 45-48 [Note]
Tight Bounds on the Average Sensitivity of k-CNF
Received: November 25, 2010
Published: March 15, 2011
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$.