Is uniform RNC contained in polylog space?

Question

Log-space-uniform NC is contained in deterministic polylog space (sometimes written PolyL). Is log-space-uniform RNC also in this class? The standard randomized version of PolyL should be in PolyL, but I don't see that (uniform) RNC is in randomized-PolyL.

The difficulty I see is that in RNC, the circuit can "look at the random bits" as much as it wants; i.e., the random inputs can have arbitrary fanout. But in the randomized version of PolyL, it's not like you get a tape of random bits you get to look at as much as you want; rather, you are only allowed to flip a coin at each time step.

Thanks!

Answer 1

Perhaps most people think that $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$ (or even that $\mathsf{RNC}=\mathsf{NC}$), but I'm skeptical about this (see the second part of my answer, below). If $\mathsf{RNC}$ is indeed contained in $\mathsf{DSPACE(polylog)}$, then it is also contained in $\mathsf{NTIME(2^{polylog})}$ (more specifically, it is in $\mathsf{DTIME(2^{polylog})}$ by exhaustive search).

Valentine Kabanets explained to me the following (folklore) argument from his paper with Russell Impagliazzo that explains why $\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$ is unlikely.

Theorem: If $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$, then either $\mathsf{NEXP}$ is not computable by Boolean circuits of size $o(2^n/n)$ (i.e. sub-maxsize by Shannon; irrelevant but see Lupanov for tightness), or Permanent is not computable by (division-free) arithmetic formulas over ${\mathbb Z}$ of quasipolynomial size.

Proof: assume $\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$. If Permanent has a quasipolynomial size formula, then we can guess and verify such a formula for Permanent using a quasipolynomial time polynomial identity tester by assumption. This places Permanent in $\mathsf{NTIME(2^{polylog})}$.

By Toda's theorem, $\Sigma_2$ is then also in $\mathsf{NTIME(2^{polylog})}$. By padding, the linear-exponential time version of $\Sigma_5$ is also in $\mathsf{NEXP}$. Hence the linear-exponential version of $\Sigma_5$ has a circuit of size $o(2^n/n)$ (i.e. submax). But, by a simple diagonalization argument, one can show that the linear-exponential version of $\Sigma_5$ requires max circuit size, which is a contradiction (by the way, this is a variant of a mid-level question for a graduate-level complexity course; okay, maybe proving that $\mathsf{EXPSPACE}$ requires max-size circuits is a simpler one). QED.

Now the unpopular direction.

We already know that randomness read many times can do something non-obvious. An interesting example can be found in "Making Nondeterminism Unambiguous" by Reinhardt and Allender (they state it in terms of non-uniformity but in principle it is about using read-many-times randomness). Another interesting example (less directly related) is "Randomness Buys Depth for Approximate Counting" by Emanuele Viola. I guess all I'm saying is that I wouldn't be surprised if the derandomization of $\mathsf{RNC}$ is not what most people would expect it to be.

(There are also a couple of other papers, like Noam Nisan's wonderful paper on read-once vs. read-many randomness, that show how to buy two-sided error with one-sided error.)

By the way, understanding how to construct PRGs fooling space-bounded models of computation with multiple accesses to their input (e.g. linear lengths Bps) is also very related to this question.

-- Periklis