Is deterministic pseudorandomness possibly stronger than randomness in parallel?

Question

Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a different name). Define the class DBPNC similarly, except that all processes have random access into a random stream of bits fixed at algorithm startup.

In other words, each process in BPNC has access to a distinct random source, while DBPNC algorithms have a shared perfectly random counter mode generator.

Do we know whether BPNC = DBPNC?

Answer 1

They are the same: BPNC = DBPNC.

Say a BPNC machine is given as input a DBPNC program to simulate. Execute the program in lock step. First assume that the indices between different steps are distinct, so that we do not need to remember old random bits. At each step, each processor asks for a random bit at a specific index into the shared stream. Compute and distribute the random bits as follows:

1. Sort the indices among the processors and remember the origin of each bit.
2. Coordinate among adjacent processors to compute the ranges of identical indices.
3. Compute each random bit on the first processor that owns it after sorting.
4. Scatter throughout the identical ranges.
5. Send back to the origin process (if necessary by reversing the sorting algorithm).

To allow processors to ask for old indices, have each processor remember the (results) of all previous sorting epochs. To check whether newly requested indices occurred in a given previous epoch, do

1. Sort the new indices.
2. Merge the lists of old and new indices (e.g., with Cole 1988).
3. Scatter appropriately.