The Average Sensitivity of Bounded-Depth Formulas
Benjamin Rossman · 2015
We show that unbounded fan-in boolean formulas of depth d + 1 and size s have average sensitivity O(1/d log s)d. In particular, this gives a tight 2Ω(d(n1/d-1)) lower bound on the size of depth d + 1 formulas computing the PARITY function. These results strengthen the corresponding O(log s)dand 2Ω(n1/d)bounds for circuits due to Boppana (1997) and Hastad (1986). Our proof technique studies a random process associated with formulas, in which the Switching Lemma is efficiently applied to subformulas.