Publications [#348681] of Benjamin Rossman

Papers Published

1. Rossman, B, The Average Sensitivity of Bounded-Depth Formulas, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2015-December (December, 2015), pp. 424-430, ISBN 9781467381918 [doi]
   (last updated on 2024/04/19)

   Abstract:
   We show that unbounded fan-in boolean formulas of depth d + 1 and size s have average sensitivity O(log s/d)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(logs)d and 2Ω(n1/d) bounds for circuits due to Boppana (1997) and Has tad (1986). Our proof technique studies a random process associated with formulas, in which the Switching Lemma is efficiently applied to sub formulas.