An Average-Case Depth Hierarchy Theorem for Boolean Circuits


Conference Paper

© 2015 IEEE. We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of AND, OR, and NOT gates. Our hierarchy theorem says that for every d ≥ 2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d - 1) circuit that agrees with f on (1/2 + on(1)) fraction of all inputs must have size exp(nΩ(1/d)). This answers an open question posed by Has tad in his Ph.D. Thesis [Has86b]. Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of Has tad [Has86a], Cai [Cai86], and Babai [Bab87]. We also use our result to show that there is no 'approximate converse' to the results of Linial, Mansour, Nisan [LMN93] and Boppana [Bop97] on the total influence of constant-depth circuits, thus answering a question posed by Kalai [Kal12] and Hatami [Hat14]. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Full Text

Duke Authors

Cited Authors

  • Rossman, B; Servedio, RA; Tan, LY

Published Date

  • December 11, 2015

Published In

Volume / Issue

  • 2015-December /

Start / End Page

  • 1030 - 1048

International Standard Serial Number (ISSN)

  • 0272-5428

International Standard Book Number 13 (ISBN-13)

  • 9781467381918

Digital Object Identifier (DOI)

  • 10.1109/FOCS.2015.67

Citation Source

  • Scopus