Benjamin Rossman: The Average Sensitivity Bounded-Depth Formulas

Abstract: Hastad (1986) proved an exp( n^{1/d} ) lower bound on the size of depth d+1 (unbounded fan-in) boolean *circuits* computing the PARITY function.  In recent work to appear in FOCS 2015, we prove a stronger exp( d*n^{1/d} ) lower bound for depth d+1 *formulas*.  (More generally, we show that depth d+1 formulas of size S have average sensitivity O( log S / d )^d.)  As a corollary, we separate complexity classes {poly-size depth d(n) circuits} and {poly-size depth d(n) formulas} for all d(n) = o(log n).  Our proof technique studies a random process in which Hastad’s Switching Lemma is applied to boolean formulas in an efficient manner.