The Average Sensitivity of Bounded-Depth Formulas
Publication
, Conference
Rossman, B
Published in: Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs
December 11, 2015
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.
Duke Scholars
Published In
Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs
DOI
ISSN
0272-5428
Publication Date
December 11, 2015
Volume
2015-December
Start / End Page
424 / 430
Citation
APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2015). The Average Sensitivity of Bounded-Depth Formulas. In Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs (Vol. 2015-December, pp. 424–430). https://doi.org/10.1109/FOCS.2015.33
Rossman, B. “The Average Sensitivity of Bounded-Depth Formulas.” In Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs, 2015-December:424–30, 2015. https://doi.org/10.1109/FOCS.2015.33.
Rossman B. The Average Sensitivity of Bounded-Depth Formulas. In: Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs. 2015. p. 424–30.
Rossman, B. “The Average Sensitivity of Bounded-Depth Formulas.” Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs, vol. 2015-December, 2015, pp. 424–30. Scopus, doi:10.1109/FOCS.2015.33.
Rossman B. The Average Sensitivity of Bounded-Depth Formulas. Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs. 2015. p. 424–430.
Published In
Proceedings Annual IEEE Symposium on Foundations of Computer Science Focs
DOI
ISSN
0272-5428
Publication Date
December 11, 2015
Volume
2015-December
Start / End Page
424 / 430