# What are the gap functions in the $AC$ hierarchy?

Hastad had in 1985 shown that PARITY(n) if it has to be evaluated by a depth$-d$ $AC^0$ circuit needs a size $\Theta(2^{n^{\frac{1}{d-1}}})$. But PARITY is in $NC^1$ and PARITY is also the negation of the MOD2 and hence this shows that the following inclusions are strict, $AC^0 \subset AC^0[2] \subset NC^1$.

• If I understand right then Razborov's 1987 result of exponential size lower bound for MAJORITY for $AC^0[2]$ or Smolensky's similar result in 1986 for MOD3 for $AC^0[2]$ do not in anyway strengthen the inclusion consequence of Hastad's result. Am I right?

• But do we know whether $AC^i$ vs $AC^{i+1}$ separation is strict or not? Like do we know of functions which are exponentially sized for $AC^i$ but can be computed by polynomial sized circuits for $AC^{i+1}$?

## 1 Answer

Razborov-Smolensky prove that the classes $\mathrm{AC}^0[p]$ and $\mathrm{AC}^0[q]$ are incomparable when $p$ and $q$ are distinct primes, which also implies $$\mathrm{AC}^0\subsetneq\mathrm{AC}^0[p]\subsetneq\mathrm{ACC}$$ for prime $p$. That's about it: it is consistent with the present knowledge that uniform $\mathrm{AC}^0[6]$ coincides with all of the polynomial hierarchy PH, so no classes in between have been unconditionally separated (uniformly or nonuniformly).

• Thanks! (1) Could you kindly explain what you mean by "not unconditionally separated"? Does that mean that there could be a strict inclusion from $AC^i$ to $AC^{i+1}$ but just that we don't know? (2) Could you kindly give some reference to understand the proof of this statement that uniform AC^0[6] coincides with all of PH"? – gradstudent Oct 2 '16 at 18:44
• (1) Yes. Most people expect that $\mathrm{AC}^{i+1}$ is strictly larger than $\mathrm{AC}^i$, but no one can prove it. (2) I didn't write that uniform $\mathrm{AC}^0[6]$ coincides with PH (again, the expectation is that it does not), I wrote that it is consistent with the present knowledge. This is not a statement to be proved, it's just an observation in plain English that there is no published proof that the two classes are different (or of anything that would easily imply it). – Emil Jeřábek supports Monica Oct 2 '16 at 19:15
• Thanks! And also for any of the $AC^i$s or $NC^i$s is the function space completely characterized? Like do we know which functions are in it and which are not? Can you point me to some reference which gives the state of the art in this matter? – gradstudent Oct 3 '16 at 0:16
• It's not quite clear to me what kind of characterization you are after, however I'd say that we have no clue what languages are or are not in $\mathrm{AC}^i$ (for $i>0$). That is, we can show for particular languahes that they are in this class by using some form of its definition, but there are no useful techniques for proving that a language is outside. Which is why we can't separate the classes in the first place. – Emil Jeřábek supports Monica Oct 4 '16 at 15:52
• Thanks! Could you kindly give me a good reference to understand the state of the art about this? (I know the kind of stuff in say the book Arora-Barak book) – gradstudent Oct 4 '16 at 21:05