Math @ Duke

Publications [#348673] of Benjamin Rossman
Papers Published
 Håstad, J; Rossman, B; Servedio, RA; Tan, LY, An averagecase depth hierarchy theorem for boolean circuits,
Journal of the Acm, vol. 64 no. 5
(August, 2017) [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 Hastad in his Ph.D. thesis (Hastad 1986b). Our averagecase 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 boundeddepth circuits. 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

