28
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Ryan O'Donnell Aug 1 '13 at 18:33
  • 2
    $\begingroup$ Corollary 4.13 in the paper $\endgroup$ – sdcvvc Aug 2 '13 at 19:41
  • $\begingroup$ @sdvvc: Make that an answer? $\endgroup$ – Joshua Grochow Aug 3 '13 at 1:05
  • $\begingroup$ @JoshuaGrochow We know $NC=PSPACE$ is not possible. However is $RNC=P=BPP=NP=PSPACE$ possible? $\endgroup$ – T.... Jul 23 '18 at 0:04
18
+25
$\begingroup$

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

$\endgroup$
  • $\begingroup$ "two-sided error for zero-sided error". $\endgroup$ – user17164 Aug 3 '13 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.