Theory of Computing
-------------------
Title : Tight Bounds on the Average Sensitivity of k-CNF
Authors : Kazuyuki Amano
Volume : 7
Number : 4
Pages : 45-48
URL : http://www.theoryofcomputing.org/articles/v007a004
Abstract
--------
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.