The Average Sensitivity of Bounded-Depth Formulas

We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity $${O(\frac{1}{d} \log s)^d}$$ . In particular, this gives a tight $${2^{\Omega(d(n^{1/d}-1))}}$$ lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding $${2^{\Omega(n^{1/d})}}$$ and $${O(\log s)^d}$$ bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.