# An Average-Case Depth Hierarchy Theorem for Boolean Circuits

Published

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