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