Math @ Duke

Publications [#348680] of Benjamin Rossman
Papers Published
 Rossman, B; Servedio, RA; Tan, LY, An AverageCase Depth Hierarchy Theorem for Boolean Circuits,
Annual Symposium on Foundations of Computer Science (Proceedings), vol. 2015December
(December, 2015),
pp. 10301048, ISBN 9781467381918 [doi]
(last updated on 2022/05/21)
Abstract: We prove an averagecase 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 nvariable Boolean function f, computed by a linearsize depthd 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 averagecase 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 constantdepth 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

