An Average-Case Depth Hierarchy Theorem for Boolean Circuits

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 + o n (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 [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 Hastad [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.

Authors

• Benjamin Rossman
• Rocco A. Servedio
• Li-Yang Tan

Keywords

• Polynomials
• Correlation
• Complexity theory
• Boolean functions
• Logic gates
• Computational modeling
• Integrated circuit modeling
• Boolean Circuit
• Conjecture
• Probability 1
• Explicit Function
• Boolean Function
• Random Projection
• NOT Gate
• Random Oracle
• High Probability
• Lower Bound
• Uniform Distribution
• Decision Tree
• Input Variables
• Family Functioning
• Product Distribution
• Disprove
• Sequencing Project
• Over Space
• Individual Projects
• Constant Depth
• Circuit Size
• OR Gate
• Subsequent Projects
• Delicate Task
• Small-depth circuits
• average-case
• depth hierarchy theorem
• Polynomial Hierarchy
• random projections