What are some of the best circuit separations that we know of and that we suspect?

Question

We know that $\mathsf{non-uniformAC^0\subsetneq PSPACE}$, $\mathsf{non-uniformACC^0\subsetneq NEXP}$. We know that $\mathsf{uniformACC^0=PH}$ is a possibility.

What are some of circuit separations that we know of?

What are some circuit separations that seem farthest apart but cannot be separated? By this question I mean that even though $\mathsf{uniformTC^0\subsetneq PH}$ is a possibility, an answer with $\mathsf{uniformACC^0\subsetneq PH}$ suffices since $\mathsf{uniformACC^0\subsetneq uniformTC^0}$ is hypothesized.

Answer 1

For all uniform classes $\operatorname{UF}$, for essentially any non-uniform class $\operatorname{NU}$, one will
have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \:$, $\:$ since $\operatorname{NU}$ should be uncountable and $\operatorname{UF}$ is countable.
("Proof:" $\;\;\;$ By any reasonable definition of being uniform, for a language to be in $\operatorname{UF}$
there must be something in a particular at-most-countable set of things such that the
thing determines the language, so there are at most countably many languages in $\operatorname{UF}$.
On the other hand, for each subset $S$ of $\:\{\hspace{-0.03 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.04 in}\}\:$,$\:$ the definition of $\operatorname{NU}$ should
mean that [the language consisting of exactly the strings whose length is in $S\hspace{.02 in}$] is in $\operatorname{NU}$.
In that case, since those languages are all different, $\operatorname{UF}$ will be uncountable.
"Therefore," one will have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \;$.)

In particular, $\;\;\; \mathsf{non-uniformAC^0} \: \not\subseteq \: \operatorname{PSPACE} \;\;\;$ and
$\mathsf{non-uniformACC^0} \: \not\subseteq \: \operatorname{NEXP} \;\;\;$, $\;\;\;$ so both claims in your initial sentence are false.
It is far more interesting to ask which uniform classes
are subsets of which non-uniform classes.


$\operatorname{REG}$ $\: \not\subseteq \: \mathsf{non-uniformAC^0} \;\;\;$, $\;\;\;$ since $\;\;\;$ parity $\: \not\in \: \mathsf{non-uniformAC^0}$ $\:\:\:\:$.
$\operatorname{NEXP} \: \not\subseteq \: \mathsf{non-uniformACC^0} \;\;\;$; $\;\;\;$ which your question on cstheory was asking about.
$\operatorname{MA_{exp}}$ $\cap \hspace{.03 in}\operatorname{co-MA_{exp}}$ $\: \not\subseteq \:$ $\operatorname{P/poly}$ $\;\;\;$, $\;\;\;$ by page 16 of this paper.
$\operatorname{AM_{exp}}$ $\: \not\subseteq \:$ $\operatorname{(NP\cap coNP)/poly}$ $\;\;\;$, $\;\;\;$ by this paper. $\;\;\;\;\;$ (The right-hand-side of
the last non-containment is likely smaller than the class one would think it means.)
This paper shows that $\operatorname{MA_{exp}}$ can't be decided by circuits with "half-exponential" size.