Family 103Theoretical computer scienceLeanSep 23, 2026

Exact Derandomization of Logarithmic Space: L = RL = BPL

What this paper proves

Every language decided by a polynomial-time randomized logarithmic-space machine with one-sided or two-sided bounded error is decided by a deterministic logarithmic-space machine, so

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

. The key step is a deterministic polynomial-time logspace algorithm that approximates the machine's acceptance probability to within

(n+2)^{-d}

for any fixed

d

, using a compression of additive row estimates whose total error stays within a fixed precision budget. This settles the derandomization problem for bounded-error logarithmic space: randomness gives no extra power there.

Main theorem

theoremnovelLogarithmic space equals randomized logarithmic spacethm:main

Deterministic logarithmic space equals one-sided-error randomized logarithmic space, which equals two-sided-error bounded-error randomized logarithmic space:

\mathrm{L}=\mathrm{RL}=\mathrm{BPL}

Theorem 1.1 · as stated in the paper

\Lclass=\RL=\BPL.

Where the new idea lives · 4 novel steps (one is the main theorem)

Theorem 1.2Deterministic approximation of acceptance probability

Approximates acceptance probability within

2^{-q}

in space

O(\log n+q)

Proposition 8.5Compression preserves row error budget

Compressed rows are within

C_{\rm buf}c_*2^{-p}

of the true outputs in

s

-norm

Theorem 12.1Deterministic logspace approximation of acceptance probability

Deterministic logspace outputs

z_x

with

|z_x-p_{\mathcal M}(x)|\le(n+2)^{-d}

Shape of the proof

novel otherOpen the graph →

164

statements mapped

sections

novel steps

friction flags

Map

The proof as a tree and a dependency graph. Start at the top and click down.

Ask

Questions answered with citations to the map you can click.