The relationship between average sensitivity, clause size, and solution density

演讲人: Dominik Scheder Aarhus University
时间: 2013-06-07 14:00-2013-06-07 15:00

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.