The Average Sensitivity of Bounded-Depth Formulas

Journal Article

© 2017, Springer International Publishing AG. We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity O(1dlogs)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 2Ω(n1/d) and O(log s) d bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.

Full Text

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • June 1, 2018

Published In

Volume / Issue

  • 27 / 2

Start / End Page

  • 209 - 223

Electronic International Standard Serial Number (EISSN)

  • 1420-8954

International Standard Serial Number (ISSN)

  • 1016-3328

Digital Object Identifier (DOI)

  • 10.1007/s00037-017-0156-0

Citation Source

  • Scopus