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
Published: March 15, 2011
Keywords: Boolean functions, sensitivity, influence, conjunctive normal form
ACM Classification: F.1.3
AMS Classification: 68R05, 68Q15
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$.