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 Introduction

Statement (paper)

L=RL=BPL. \Lclass=\RL=\BPL.

In plain English

Deterministic logarithmic space equals one-sided-error randomized logarithmic space, which equals two-sided-error bounded-error randomized logarithmic space: L=RL=BPL\mathrm{L}=\mathrm{RL}=\mathrm{BPL}.

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.

Uses

thmDeterministic logspace approximation of acceptance probability

Used by

Nothing in the paper

Sources

PaperOpen
Section
§1 Introduction
Page
—
Label
thm:main
Line
sections/introduction.tex:28
Leannot aligned

Phase 2 aligns this node to a Lean declaration.