theoremnovel
Logarithmic space equals randomized logarithmic space
Shows L = RL = BPL: randomness adds no power in logarithmic space
the headline result
Theorem·
thm:main·§1 IntroductionStatement (paper)
In plain English
Deterministic logarithmic space equals one-sided-error randomized logarithmic space, which equals two-sided-error bounded-error randomized logarithmic space: .
Why it's here
This is the paper's main result: randomness gives no extra power in logarithmic space. The context only shows that it builds on the fixed-precision theorem (Theorem 12.1), which handles approximation at a fixed inverse-polynomial accuracy. The explanation of that dependency is not available here, so the exact derivation is not described.
Classified novel:
This is the paper's headline result. Prior work gave only partial derandomizations: BPL in L^{3/2} (Saks–Zhou), Nisan's generator, and Reingold's SL = L. None of these placed BPL in L, so this result follows from the paper's new fixed-precision deterministic logspace approximation theorem.