There are many streaming algorithms with sublinear randomized space but linear deterministic space. Does $P=BPP$ have anything to do with derandomizing space and more importantly but not related to streaming does derandomizing time have anything to do with $L=RL$?

  • 2
    $\begingroup$ Here's a tenuous connection. $\mathbf{P} = \mathbf{BPP}$ implies some circuit lower bounds. Suitable circuit lower bounds imply $\mathbf{L} = \mathbf{RL}$. (The two circuit lower bounds are not the same.) $\endgroup$ – William Hoza Apr 30 '18 at 21:40

Your Answer

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

Browse other questions tagged or ask your own question.