An average-case depth hierarchy theorem for Boolean circuits

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

We prove an average-case depth hierarchy theorem for Boolean circuits over the standard basis of $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$ gates. Our hierarchy theorem says…