Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#348680] of Benjamin Rossman

Papers Published

  1. Rossman, B; Servedio, RA; Tan, LY, An Average-Case Depth Hierarchy Theorem for Boolean Circuits, Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2015-December (December, 2015), pp. 1030-1048, ISBN 9781467381918 [doi]
    (last updated on 2022/05/21)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320