Sensitivity of boolean functions, abstract harmonic analysis, and circuit complexity

We exploit the notion of sensitivity of Boolean functions to find complexity results. We first analyze the distribution of the average sensitivity over the set of all the n-ary Boolean functions, and show some applications of this analysis. We then use harmonic analysis on the cube to study how the average sensitivity of a Boolean function propagates if the function corresponds, e.g., to an oracle available to compute another function. To do this, we analyze the sensitivity of the composition of Boolean functions. We find the relation existing between a complexity measure for symmetric functions introduced in [FKPS 85] and the average sensitivity. We use this relation to prove that symmetric functions in AC° have exponentia11y decreasing average sensitivity. This is, in the special case of symmetric functions, a substantial improvement over the characterization given in [LMN 89].