Family 103Theoretical computer scienceLeanDigested

Exact derandomization of logarithmic space: $\mathsf L=\mathsf{RL}=\mathsf{BPL}$

Proves

\mathsf L=\mathsf{RL}=\mathsf{BPL}

, resolving derandomization for bounded-error logarithmic-space computation. An effective compiler converts each randomized polynomial-time logarithmic-space machine deciding a language with one-sided or two-sided error into a deterministic logarithmic-space decider with explicit polynomial running-time bounds.

Manuscripts in this family · 1

Exact derandomization of logarithmic space: L = RL = BPL

Sep 23, 2026·paper.pdfDigestedLean

We prove

\mathsf L=\mathsf{RL}=\mathsf{BPL}

, resolving the derandomization problem for polynomial-time randomized logarithmic space.

Full abstract

Read the map PDF on GitHub LaTeX source

Exact derandomization of logarithmic space: L=RL=BPL\mathsf L=\mathsf{RL}=\mathsf{BPL}L=RL=BPL

Manuscripts in this family · 1

Exact derandomization of logarithmic space: L = RL = BPL

Exact derandomization of logarithmic space: $\mathsf L=\mathsf{RL}=\mathsf{BPL}$