BOOLEAN FUNCTIONS WITH LOW AVERAGE SENSITIVITY DEPEND ON FEW COORDINATES

Consider a function f:{0, 1}(n) --> {0, 1}. The sensitivity of a point v is an element of {0,1}(n) is \{v' :f(v')not equal f(v), dist(v,v')= 1}\, i.e. the number of neighbors of the point in the discrete cube on which the value of f differs. The average sensitivity of f is the ave rage of the sensitivity of all points in {0, 1}(n). (This can also be interpreted as the sum of the influences of the n variables on f, or a s a measure of the edge boundary of the set which f is the characteris tic function of.) We show here that if the average sensitivity of f is k then f can be approximated by a function depending on c(k) coordina tes where c is a constant depending only on the accuracy of the approx imation but not on n. We also present a more general version of this t heorem, where the sensitivity is measured with respect to a product me asure which is not the uniform measure on the cube.