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