theoremnovel

Deterministic logspace approximation of acceptance probability

Deterministic logspace outputs zxz_x with ∣zx−pM(x)∣≤(n+2)−d|z_x-p_{\mathcal M}(x)|\le(n+2)^{-d}
main derandomization step behind L=RL=BPL
Theorem·thm:fixed-precision·§12 Derandomization and quantitative consequences

Statement (paper)

Fix a randomized machine M\mathcal M with polynomial worst-case running time and O(log⁡(n+2))O(\log(n+2)) work space, and fix an integer d≥1d\ge1. There is a uniform deterministic transducer that, on every input xx of length nn, outputs a dyadic rational zx∈[0,1]z_x\in[0,1] with ∣zx−pM(x)∣≤(n+2)−d. |z_x-p_{\mathcal M}(x)|\le(n+2)^{-d}. Its work space and output length are O(log⁡(n+2))O(\log(n+2)), and its running time is polynomial in n+2n+2. The constants may depend on M\mathcal M and dd, but not on the input.

In plain English

For a polynomial-time randomized machine M\mathcal M with O(log⁡(n+2))O(\log(n+2)) work space and any fixed d≥1d\ge1, a uniform deterministic logspace transducer running in polynomial time outputs a dyadic zx∈[0,1]z_x\in[0,1] with ∣zx−pM(x)∣≤(n+2)−d|z_x-p_{\mathcal M}(x)|\le(n+2)^{-d}. The output has length O(log⁡(n+2))O(\log(n+2)), and the constants may depend on M\mathcal M and dd but not on the input.

Why it's here

This is the paper's main derandomization step: it gives inverse-polynomial additive approximation of acceptance probability with no promise on pM(x)p_{\mathcal M}(x), which the main equality L=RL=BPL\mathsf L=\mathsf{RL}=\mathsf{BPL} and its corollaries then use. The proof reduces the machine to a substochastic system, takes the hierarchy reward at a suitable stage as a one-sided approximation, and recovers it deterministically from the fixed-precision estimators by an enumerable conditional environment and a binary-search median, within logarithmic space and polynomial time.
Classified novel:
This is the paper's main derandomization theorem: deterministic logspace inverse-polynomial approximation of acceptance probability with no promise. Prior work such as Saks–Zhou (BPL ⊆ L^{3/2}) and Nisan's generator gives only superlogarithmic space, so this step itself carries the new L = BPL result.

Uses

lemRandomized logspace machines as substochastic systemspropHierarchy reward approximates base acceptance probabilitylemRank channel retention estimatesthmFixed-precision estimators meet error boundlemConditional moment bound at a specified startthmUniform numerical interface for arithmetic recipesthmController interfaces have restoring O(B)-space implementations

Used by

thmLogarithmic space equals randomized logarithmic spacethmDeterministic approximation of acceptance probabilitycorPromise BPL equals promise LcorDeterministic search for accepting computationsthmEffective compiler from randomized to deterministic logspaceclaimFixed deterministic library decides interpreter promise

Inside the proof

claimStage-L reward approximates acceptance probabilityclaimPrecision choice beats coordinate factor NclaimTruncated digits give accurate dyadic valuesclaimConditional environment law is enumerableclaimBinary-search median is accurateclaimOuter computation uses O(B) space totalclaimTransducer runs in polynomial time

Sources

PaperOpen
Section
§12 Derandomization and quantitative consequences
Page
—
Label
thm:fixed-precision
Line
sections/conclusion.tex:18
Leannot aligned

Phase 2 aligns this node to a Lean declaration.