Volume 7 (2011) Article 4 pp. 45-48 [Note]
Tight Bounds on the Average Sensitivity of k-CNF
Published: March 15, 2011
[PDF (158K)]    [PS (390K)]    [PS.GZ (160K)]
[Source ZIP]
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$.