Skip to main content

An average-case depth hierarchy theorem for boolean circuits

Publication ,  Journal Article
Håstad, J; Rossman, B; Servedio, RA; Tan, LY
Published in: Journal of the ACM
August 1, 2017

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 Hastad in his Ph.D. thesis (Hastad 1986b). 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 Hastad (1986a), Cai (1986), and Babai (1987). We also use our result to show that there is no "approximate converse" to the results of Linial, Mansour, Nisan (Linial et al. 1993) and (Boppana 1997) on the total influence of bounded-depth circuits. A key ingredient in our proof is a notion of random projections which generalize random restrictions.

Duke Scholars

Published In

Journal of the ACM

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

August 1, 2017

Volume

64

Issue

5

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Håstad, J., Rossman, B., Servedio, R. A., & Tan, L. Y. (2017). An average-case depth hierarchy theorem for boolean circuits. Journal of the ACM, 64(5). https://doi.org/10.1145/3095799
Håstad, J., B. Rossman, R. A. Servedio, and L. Y. Tan. “An average-case depth hierarchy theorem for boolean circuits.” Journal of the ACM 64, no. 5 (August 1, 2017). https://doi.org/10.1145/3095799.
Håstad J, Rossman B, Servedio RA, Tan LY. An average-case depth hierarchy theorem for boolean circuits. Journal of the ACM. 2017 Aug 1;64(5).
Håstad, J., et al. “An average-case depth hierarchy theorem for boolean circuits.” Journal of the ACM, vol. 64, no. 5, Aug. 2017. Scopus, doi:10.1145/3095799.
Håstad J, Rossman B, Servedio RA, Tan LY. An average-case depth hierarchy theorem for boolean circuits. Journal of the ACM. 2017 Aug 1;64(5).

Published In

Journal of the ACM

DOI

EISSN

1557-735X

ISSN

0004-5411

Publication Date

August 1, 2017

Volume

64

Issue

5

Related Subject Headings

  • Computation Theory & Mathematics
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences