Exact derandomization of logarithmic space: $\mathsf L=\mathsf{RL}=\mathsf{BPL}$

The explanation

Picture an input a million symbols long. To point at one symbol, a computer needs about 20 bits, because 2^20 is 1,048,576. A logarithmic-space machine is allowed only a fixed number of such pointers and counters. Logarithmic space means memory that grows like the number of digits of the input length. Give the machine three 20-bit counters. Then it has at most 2^60 memory states, about 1.15 × 10^18. That is roughly the input length cubed. A machine that never repeats a state must stop within that many steps. So these machines also run in polynomial time, meaning a fixed power of the input length.

Now let the machine flip fair coins as it works. Suppose it runs for a million squared steps and flips a coin each step. That is 10^12 random bits, far more than it can remember. Each coin is fresh, and the machine cannot store them all. The question is whether those coins add any power. Could a machine with the same tiny memory, and no coins, always reach the same answers? Trying every coin sequence is hopeless: there are 2^(10^12) of them.

Three families of problems name the question. L holds the problems a coin-free machine solves in logarithmic space. RL allows coins and polynomial time with one-sided error. Such a machine never says yes to a no-instance, and says yes to a yes-instance at least half the time. BPL allows two-sided error. It says yes with probability at most 1/3 on no-instances and at least 2/3 on yes-instances. The paper proves that all three families are the same: L = RL = BPL.

The question is old. John Gill developed the theory of coin-flipping machines in 1977. In 1979, Aleliunas, Karp, Lipton, Lovász and Rackoff found coin-flipping methods for maze connectivity. They explicitly asked whether such machines could be made deterministic in logarithmic space. A main line of attack replaces many coin flips with a short seed. In 1992, Noam Nisan built a generator whose seed has length of order log² n. In our example that is about 397 bits, ignoring constant factors. Trying every seed then takes more than polynomial time.

Later work cut the memory but never reached logarithmic space in general. Nisan's 1994 method ran in polynomial time with log² n space. Michael Saks and Shiyu Zhou reached log^(3/2) n space in 1999. In our example that is about 89 bits instead of 20. William Hoza improved this slightly in 2021. Special cases fell earlier. Omer Reingold's logarithmic-space method for undirected connectivity appeared in 2005. Those special methods relied on structure that general machines lack.

The paper's route is to estimate the machine's chance of saying yes. It builds a large but finite family of estimates, each named by a short description. More than three quarters of them are accurateSource 1. Each one can be computed deterministically in logarithmic space, and each computation always stops. The machine then tries every description and takes the median. The hard part is memory. The estimates are built in nested levels. Keeping a full address at every level would cost too much. The paper instead compares addresses by short fingerprints, which keeps the total memory logarithmicSource 2.

Here is what that buys in practice. The final estimate is off by less than 1/8 on most descriptions, and so is their medianSource 3. On a no-instance the true chance is at most 1/3, so the estimate stays below 11/24, about 0.458. On a yes-instance it is at least 2/3, so the estimate stays above 13/24, about 0.542. Comparing with 1/2 therefore gives the right answer every timeSource 4. The paper also claims a compiler. It is said to turn a described coin-flipping machine into a deterministic one, with explicit memory and time boundsSource 5.

The result has limits. It covers coin-flipping machines with a polynomial time limit on every runSource 6. Machines without that time limit are a broader setting, and the paper does not claim them. Its general estimator can reach any accuracy 2^-q. But its running time then grows exponentially in q, so very fine estimates stay slowSource 7.

How sure is this? A computer proof checker called Lean has a formal proof of L = RL = BPL. It uses binary inputs and an explicit Turing-machine model with logarithmic workspace. The compiler and its numerical time bounds are not part of that checked statement. No specialists have published a review yet.

What it doesn't show. This does not cover coin-flipping machines without a polynomial time limit, or make very fine probability estimates fast.