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$.