A boolean function f: {0,1}^n -> {0,1} is sensitive to a coordinate i at point x if flipping the i-th coordinate of x changes the value of f. That is, if f(x) != f(x + e_i). The sensitivity of a boolean function f at point x, written S(f,x), is the number of coordinates to which f is sensitive at x. This is an integer between 0 and n. The average sensitivity of a function, S(f), is, well, the average of S(f,x) over all x.

In 2011, Kazuyuki Amano proved that a k-CNF formula has average sensitivity at most k. Note that this bound does not depend on n, the number of variables in the formula.

We determine the exact relationship between the clause width k, the density of f (fraction of points on which f is 1) and the average sensitivity of f. We also determine the exact relationship for

monotone k-CNF formula.
 

 

This is joint work with Li-Yang Tan.