An average-case depth hierarchy theorem for Boolean circuits


May 15, 2015


Li-Yang Tan


UC Berkeley


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 Hastad in his Ph.D. thesis. 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, Cai, and Babai. We also use our result to show that there is no “approximate converse” to the results of Linial, Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus answering a question posed by O’Donnell, Kalai, and Hatami. A key ingredient in our proof is a notion of random projections which generalize random restrictions. Joint work with Ben Rossman and Rocco Servedio.


Li-Yang Tan

Li-Yang Tan is Microsoft Research Fellow at the Simons Institute at UC Berkeley. He received his Ph.D. from Columbia University, where he was advised by Rocco Servedio. His research is in theoretical computer science, with an emphasis on analysis of Boolean functions, concrete complexity, and learning theory. While in graduate school he spent summer 2012 visiting Ryan O’Donnell at CMU, spring 2013 visiting Johan HÃ¥stad at KTH, and summers 2013 and 2014 interning with Boaz Barak and Parikshit Gopalan at MSR.