# Conditional Results on Bounded Depth Circuit Hierarchy

$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.

$AC$-hierarchy is $\bigcup _{i =0}^{\infty} AC^{i}$ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with AND OR NOT gates. $ACC$-hierarchy is obtained by adding $AC$-hierarchy modulo gates computing the number of $1$'s in a input mod $q$ is $0$ or not for fixed integer $q$. $\mathsf{TC}$-hierarchy is $\bigcup _{i=0}^{\infty} TC^{i}$ , where $TC^{i}$ is the $i$-th level of the hierarchy: a family of $\mathsf{poly} (n)$-size and $O(\log ^{i}n)$ depth circuits with threshold gates. We consider classes of nonuniform circuits

I am interested in conditional results saying that if I were a bird, then blah blah...

More specifically, let $\mathcal{A,B}$ be large compleixty classes satisfying $\mathcal{A} \subseteq \mathcal{B}$ and let $H^{i}$ be the $i$^th level of a bounded depth circuit hierarchy $H$. Is there a result saying that if $H \supseteq \mathcal{B}$ then $H^{i} \supseteq \mathcal{A}$ for a fixed $i$ ?

More concretely, is there a well know complexity class $\mathcal{L}$ with the result that if $\mathsf{NEXP} \subseteq H$ then $\mathcal{L} \subseteq H^{0}$ ?

• Assuming we are talking about uniform versions, all of these hierarchies are inside $\mathsf{P}$ which is strictly contained in $\mathsf{Exp}$. So you can get any statement by that assumption. – Kaveh May 2 '13 at 22:52
• If you parameterize the classes with size in place of depth then we have: Eric Allender and Michal Koucký, "Amplifying Lower Bounds by Means of Self-Reducibility", 2008 – Kaveh May 16 '13 at 16:01