<p>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).</p>

<p>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.</p>

<p><strong>Theorem:</strong> <em>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.</em></p>

<p><em>Proof:</em> 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})}$.</p>

<p>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). <strong>QED.</strong></p>

<p>Now the unpopular direction. </p>

<p>We already know that randomness read many times can do something non-obvious. An interesting example can be found in "<a href="http://epubs.siam.org/doi/abs/10.1137/S0097539798339041">Making Nondeterminism Unambiguous</a>" 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 "<a href="http://dx.doi.org/10.1109/FOCS.2011.19">Randomness Buys Depth for Approximate Counting</a>" 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.</p>

<p>(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.)</p>

<p>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.</p>

<p>-- Periklis</p>

CC BY-SA 3.0
2013-08-03T06:18:59.870Z
"two-sided error for zero-sided error".
user17164
CC BY-SA 3.0
2013-08-03T05:44:48.907Z
2013-08-06T20:23:25.040Z
2013-08-06T20:23:25.040Z
user17164
<p>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.  </p>

<p>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.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-08-01T18:33:39.043Z
Periklis Papakonstantinou has emailed me precisely the kind of answer I was looking for.  He told me that Valentine Kabanets told him that one can use Kabanets--Impagliazzo to show that uniform-RNC in PolyL would imply certain circuit lower bounds for either NEXP or Permanent.  Perhaps one of them might post the argument here.
Ryan O'Donnell
CC BY-SA 3.0
2013-08-02T19:41:36.273Z
Corollary 4.13 in the [paper](http://www.cs.sfu.ca/~kabanets/papers/poly_derand.pdf)
sdcvvc
CC BY-SA 3.0
2013-08-03T01:05:30.390Z
@sdvvc: Make that an answer?
Joshua Grochow
CC BY-SA 4.0
2018-07-23T00:04:30.073Z
@JoshuaGrochow We know $NC=PSPACE$ is not possible. However is $RNC=P=BPP=NP=PSPACE$ possible?
Turbo
<complexity-classes><randomized-algorithms>
Is uniform RNC contained in polylog space?
Ryan O'Donnell
# Is uniform RNC contained in polylog space?

(Asked by: username_0 on 2013-07-24)

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!

**Tags:** complexity-classes, randomized-algorithms

> **Comments:**
> **username_0**: Periklis Papakonstantinou has emailed me precisely the kind of answer I was looking for.  He told me that Valentine Kabanets told him that one can use Kabanets--Impagliazzo to show that uniform-RNC in PolyL would imply certain circuit lower bounds for either NEXP or Permanent.  Perhaps one of them might post the argument here.  
> **username_1**: Corollary 4.13 in the [paper](http://www.cs.sfu.ca/~kabanets/papers/poly_derand.pdf)  
> **username_2**: @sdvvc: Make that an answer?  
> **username_3**: @JoshuaGrochow We know $NC=PSPACE$ is not possible. However is $RNC=P=BPP=NP=PSPACE$ possible?  

---

## 1 answers

### Answer by username_4 on 2013-08-03. Score: 18 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/S0097539798339041)" 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](http://dx.doi.org/10.1109/FOCS.2011.19)" 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

> **Comments:**
> **username_4**: "two-sided error for zero-sided error".  

---

