1 · The essentials
The result concerns computers that solve yes-or-no problems while using very little working memory. Specifically, their memory allowance grows only logarithmically with the length of the input. Such computers may use random choices and be allowed a limited chance of giving the wrong answer. The manuscript’s main result says that randomness does not expand the set of problems they can solve under the stated time and memory restrictions. The repository summary also describes a procedure for converting these randomized computers into computers that give the correct answer without random choices. The conversion retains the logarithmic memory limit and comes with explicit polynomial running-time bounds. The main equality has a Lean formalization.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, imagine someone answering a yes-or-no question with a tiny scratchpad, sometimes tossing coins to decide what to do next. The result says that, for the procedures covered by its assumptions, a coin-free replacement can always answer correctly while keeping the same kind of scratchpad limit; the image does not explain how that replacement is constructed.
Why it matters
The result identifies the same collection of decision problems behind deterministic and bounded-error randomized computation under logarithmic-space and polynomial-time restrictions. The repository summary goes beyond this equality by describing an effective conversion with explicit running-time bounds. This makes the stated result about both what can be computed and how a deterministic replacement can be obtained.
2 · Going further
The precise claim is . Here denotes deterministic logarithmic-space decision, while and concern randomized logarithmic-space decision with one-sided and two-sided bounded error, respectively. The randomized machines in the supplied statement run in polynomial time. The question is whether removing their random choices forces an increase beyond logarithmic working space.
The repository summary states that an effective compiler converts each such randomized machine into a deterministic logarithmic-space decider, with explicit polynomial running-time bounds. Thus the stated conversion removes error as well as randomness. These bounds do not, by themselves, say that the replacement runs as quickly as the original machine.
The supplied abstract announces the equality but gives no argument or construction details, so the mechanism of the derandomization cannot be explained from this excerpt. The main manuscript is marked as Lean-formalized, and the main result has a Lean formalization. No companion manuscripts are supplied, and the excerpt does not specify whether the compiler and its explicit time bounds are included in the formalization.
Useful notions
- Yes-or-no decision problems
- Working memory versus running time
- Logarithmic space and polynomial time
- Randomized computation and bounded error
- Deterministic computation
What was known before / what is new
Before
The source frames derandomization for polynomial-time randomized logarithmic space as the problem being resolved. It provides no earlier results, historical chronology, or previous bounds, so it does not support a more detailed account of what was known beforehand.
New
The main result is the equality , with a Lean formalization. The repository summary also states an effective compiler from one-sided or two-sided bounded-error randomized machines to deterministic logarithmic-space deciders, together with explicit polynomial running-time bounds.
Limits and assumptions
The claim concerns language decision by polynomial-time randomized machines using logarithmic working space and having one-sided or two-sided bounded error. It does not state a result for arbitrary memory allowances, unrestricted error, or other computational tasks. The main equality has a Lean formalization, but the supplied text does not delineate its coverage of the compiler or quantitative time bounds. No proof strategy, specific polynomial bounds, companion manuscripts, or remaining open questions are provided.
Mini glossary
- Derandomization —
- Replacing a computation that uses random choices with a deterministic computation while retaining the required resource limits.
- Logarithmic space —
- A working-memory allowance bounded by a constant multiple of the logarithm of the input length.
- Polynomial time —
- A running-time allowance bounded by a polynomial in the input length.
- One-sided error —
- An error allowance under which incorrect answers can occur on only one of the two kinds of input: those whose correct answer is yes or those whose correct answer is no.
- Two-sided error —
- An error allowance under which incorrect answers can occur on both yes-inputs and no-inputs.
- Decider —
- A procedure that terminates on every input and correctly answers whether that input belongs to the language being decided.
Keywords : Derandomization · Logarithmic space · Lean formalization
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Proves , 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.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Exact derandomization of logarithmic space: L = RL = BPL
23/09/2026We prove , resolving the derandomization problem for polynomial-time randomized logarithmic space.