Math @ Duke

Publications [#348681] of Benjamin Rossman
Papers Published
 Rossman, B, The Average Sensitivity of BoundedDepth Formulas,
Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2015December
(December, 2015),
pp. 424430, ISBN 9781467381918 [doi]
(last updated on 2022/05/19)
Abstract: We show that unbounded fanin 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

