Abstract 1 Introduction 2 Proof Overview 3 Preliminaries 4 Our Error Reduction Procedure References

Improved Error Reduction for Weighted PRGs

Ben Chen ORCID School of Computer Science and AI, Tel-Aviv University, Israel    Gil Cohen ORCID School of Computer Science and AI, Tel-Aviv University, Israel    Dean Doron ORCID Faculty of Computer and Information Science, Ben-Gurion University of the Negev, Beer Sheva, Israel    Yuval Khaskelberg ORCID School of Computer Science and AI, Tel-Aviv University, Israel    Amnon Ta-Shma ORCID School of Computer Science and AI, Tel-Aviv University, Israel
Abstract

We devise an error-reduction procedure that transforms a PRG for length-n, width-w read-once branching programs with error 1/poly⁢(n) and seed length s0, over any alphabet, into a weighted PRG with seed length

s0+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w).

Using this reduction, we improve upon the state-of-the-art weighted PRG constructions of Hoza (RANDOM 2021) and Cheng and Wu (SODA 2026), achieving optimal dependence on the program’s arity while matching the best known bounds in all other parameters.

Our motivation for obtaining optimal dependence on the arity stems from a result of Cheng and Hoza (CCC 2020, ToC 2022), who showed that a PRG with optimal arity and error dependence yields a PRG with seed length O⁢(log3/2⁡n) (for, say, constant width), thereby breaking the long-standing log-squared barrier.

Keywords and phrases:
Space-bounded computation, pseudorandom generators
Category:
RANDOM
Funding:
Ben Chen: Funded by the Israel Science Foundation grant 443/22 and the Blavatnik fund.
Gil Cohen: Funded by ERC starting grant 949499 and by the Israel Science Foundation grant 2989/24.
Dean Doron: Funded in part by the Israel Science Foundation grant 857/25.
Yuval Khaskelberg: Funded by ERC starting grant 949499.
Amnon Ta-Shma: Funded by the Israel Science Foundation grant 443/22.
Copyright and License:
[Uncaptioned image] © Ben Chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, and Amnon Ta-Shma; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Pseudorandomness and derandomization
Related Version:
Full Version: https://eccc.weizmann.ac.il/report/2026/064/ [7]
Acknowledgements:
We thank William Hoza for bringing to our attention Lemma 4.9 in [10], which already proves one of the theorems stated in an earlier version of this paper. We also thank Kuan Cheng and Ruiyang Wu for a useful discussion about their work [12].
Editors:
Mohit Singh and Tom Gur

1 Introduction

The question of whether 𝐁𝐏𝐋=𝐋 is one of the central open problems in computational complexity theory [1, 3, 26]. It asks whether randomness provides additional computational power to space-bounded algorithms, or equivalently, whether every probabilistic logspace algorithm can be fully derandomized with only a constant-factor increase in space. Despite decades of intensive study, the problem remains open. Nonetheless, the prevailing belief is that 𝐁𝐏𝐋=𝐋, a conjecture supported by plausible circuit lower bounds [28, 20, 19]. Importantly, unlike in the time-bounded setting, there are currently no known barriers that rule out unconditional derandomization of 𝐁𝐏𝐋.

Progress toward this goal has been strikingly limited. Beyond a small number of landmark results, there has been essentially no improvement for several decades. Already in the work of Savitch [40] and Borodin, Cook, and Pippenger [3], it was shown that 𝐁𝐏𝐋⊆𝐋2. The only substantial strengthening of this bound was obtained by Saks and Zhou [39], who proved that 𝐁𝐏𝐋⊆𝐋3/2. This result, established nearly 30 years ago, has remained essentially unimproved to this day, with only a quite recent sub-polynomial improvement due to Hoza [22].

The primary approach to resolving 𝐁𝐏𝐋 vs. 𝐋 is via the construction of pseudorandom generators (PRGs) for read-once branching programs (BPs), which constitute the standard nonuniform model associated with space-bounded Turing machines. We refer the reader to Definition 5 for a formal definition. For present purposes, it suffices to note that the length of a BP, denoted by n, corresponds to the number of random bits read by the algorithm (and is therefore bounded by its running time), while the width w captures the space usage and is, in fact, exponential in the space bound. For naive derandomization of 𝐁𝐏𝐋 via PRGs, one should consider w=poly⁢(n).

In a seminal paper, Nisan [33] constructed an explicit ε-error PRG for BPs of length n and width w with seed length O⁢(log⁡n⋅log⁡(n⁢wε)). This construction – together with its expander-based variant due to Impagliazzo, Nisan, and Wigderson [25] – remains the state of the art in the general setting. An improvement in the regime w≫n was obtained by Armoni [2] and was recently simplified in [8], shaving a factor of log⁡(log⁡wlog⁡(n/ε)) from the seed length.111Armoni’s generator uses the classical Nisan–Zuckerman generator [34], that gives optimal seed length in the extreme regime of n=polylog⁡(w).

By contrast, an optimal PRG has seed length O⁢(log⁡(n⁢wε)); if such a generator were also space-efficient, it would immediately imply 𝐁𝐏𝐋=𝐋. Remarkably, despite more than three decades of subsequent work, Nisan’s construction has not been improved. In fact, except for the case of w=3 [31], or when additional structural restrictions are imposed on the BPs (see, e.g., [29, 16, 5, 17, 36, 18, 9]), no PRG is known to break the so-called log-squared barrier; that is, to achieve seed length o⁢(log2⁡n) for constant error ε, when w=poly⁢(n), or even when the width is as small as w=4.

Weighted pseudorandom generators

To bypass this long-standing stalemate, Braverman, Cohen, and Garg [4] introduced a new type of pseudorandom object called a weighted pseudorandom generator (WPRG). A WPRG relaxes the classical definition of a PRG while still enabling the derandomization of two-sided error probabilistic algorithms. Specifically, in a WPRG each seed is assigned a weight – which may be positive, negative, and potentially unbounded – and the desired ε-approximation is achieved via a weighted sum rather than a simple average.

In [4], the authors constructed a WPRG with an almost optimal dependence on the error parameter ε, achieving seed length O~⁢(log⁡n⋅log⁡(n⁢w)+log⁡(1/ε)). While the error parameter is taken to be constant in the most naive PRG-based approach to derandomizing 𝐁𝐏𝐋, it plays a crucial role in more refined derandomization procedures, most notably the Saks–Zhou algorithm. The latter involves multiple composition steps, necessitating small error and making the dependence on ε crucial. Indeed, Braverman et al. [4] and Chattopadhyay and Liao [6] showed that one can prove 𝐁𝐏𝐋⊆𝐋4/3 even without breaking the log-squared barrier. Concretely, they showed that such a derandomization result would follow from the existence of a space-efficient WPRG with seed length O⁢(log2⁡n+log⁡(w/ε)).

As observed in [4], WPRGs readily yield hitting sets. Consequently, their result led to the first improved construction of hitting sets for BPs since the work of Nisan [33], with a much simplified follow-up construction due to Hoza and Zuckerman [24].

Since then, WPRGs have attracted significant attention. They have inspired simpler and improved constructions [30, 6, 14, 36, 22], culminating in the WPRG of Hoza [22], which removes all double-logarithmic factors, obtaining seed length O⁢(log⁡n⋅log⁡(n⁢w)+log⁡(1/ε)) and in the very recent state-of-the-art construction of Cheng and Wu [12], which achieves further improvements in the regime w≫n.

These works incorporate ideas from fast Laplacian solvers and were also the basis for significantly improved generators for restricted models [23, 36, 9]. The limitations of these techniques have been investigated in [13]. Developments in WPRGs have led to progress on several long-standing problems. Notably, they were leveraged by Hoza to improve the Saks–Zhou derandomization mentioned above [22], and have also enabled substantial advances on the closely related problem of iterated matrix multiplication [15, 35]. Moreover, the error reduction techniques have recently been used to show that 𝐁𝐏𝐋 is contained in logspace-uniform 𝐀𝐂1 [11].

Braverman, Cohen, and Garg [4] emphasized the role of the error parameter ε, showing that simultaneously improving the seed-length dependence on both ε and w would yield a significant improvement to the Saks–Zhou algorithm, even without breaking the log-squared barrier. Moreover, such an improvement need only be achieved for WPRGs, rather than for standard PRGs. While [4] and follow-up works significantly improved the dependence on ε, progress on the width parameter w has remained much more elusive. To date, the only work in this direction that we are aware of is due to Raz and Reingold [37], which presents an intriguing, albeit seemingly stalled, approach.

Cheng and Hoza [10] proposed an intriguing approach toward breaking the log-squared barrier, showing that seed length O⁢(log3/2⁡n) can be obtained even without directly improving the dependence on either n or w. Instead, such an improvement follows from simultaneously improving the dependence of PRGs on two secondary parameters: the error ε and the program’s arity |Σ|. We discuss this result below. This underscores the somewhat surprising importance of arity dependence.

1.1 Our Result

The main result of this paper is a construction of WPRGs that achieves optimal dependence on both ε and Σ, while matching the state-of-the-art bounds in n and w. As in prior work, our WPRG is obtained via an error-reduction procedure.

Theorem 1 (see also Theorem 21).

There exists an explicit reduction that transforms a PRG for length-n, width-w branching programs with seed length s0 and error ε0=1/poly⁢(n), over any alphabet, into a WPRG with error ε and seed length

s0+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w).

Instantiating Theorem 1 with Armoni’s PRG [2], we obtain the following corollary.

Corollary 2.

There exists an explicit WPRG for length-n, width-w branching programs over alphabet Σ, achieving error ε with seed length

log2⁡|Σ|+O⁢(log⁡1ε+log2⁡n+log⁡n⋅log⁡wmax⁡(1,log⁡log⁡w−log⁡log⁡n)+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w).

Corollary 2 improves upon all known WPRGs for general branching programs, including in the regime w=nO⁢(1), where the seed length simplifies to

log2⁡|Σ|+O⁢(log⁡(1/ε)+log2⁡n).

In particular, it matches the recent construction of Cheng and Wu [12] in the parameters n,w, and ε, while improving the dependence on Σ. Although this dependence is not made explicit in [12] (nor in most prior work), it is straightforward to verify that their construction – as well as several other recent WPRGs (particularly [22], which is also state-of-the-art in the regime w=nO⁢(1)) – exhibits suboptimal dependence on Σ, typically incurring an additional multiplicative factor of log⁡(1/ε)log⁡n.222Specifically, the recent work of Cheng and Wu incurs an additional multiplicative factor of log⁡(n/ε)log⁡(n⁢w). See [12, Theorem 3.2] in the latest arXiv revision. We also note that in the n=polylog⁡(w) regime, there exists an 2−log0.99⁡w≪ε≪1/poly⁡(w) for which the [12] construction achieves a quadruple-log savings over our construction.

By contrast, some earlier WPRG constructions (e.g., [4, 14]), while slightly inferior in overall seed length, achieve optimal dependence on Σ. Thus, the contribution of Corollary 2 is to attain optimal dependence on Σ while matching the best known bounds in all other parameters. Moreover, our construction and its analysis appear to be simpler than those of [12], which rely on “weighted pseudorandom reductions” – a sequence of alphabet-reduction and length-reduction steps combined with different PRGs and WPRGs. Furthermore, in the regime w=nO⁢(1), our construction is significantly simpler, and is comparable in simplicity to [22].

As discussed above, our motivation for achieving optimal dependence on the alphabet size stems from its implications for breaking the log-squared barrier [10]. We provide an alternative proof of this implication that requires truly optimal dependence on the alphabet, namely log2⁡|Σ|, as achieved in Corollary 2 for WPRGs. We prove

Theorem 3.

Assume there exists an explicit PRG with seed length

log2⁡|Σ|+O⁢(log⁡n⋅log⁡(n⁢w)+log⁡(1/ε)).

Then there exists an explicit PRG with seed length333Using error reduction, one can obtain linear dependence on log⁡(1/ε) at the cost of producing a WPRG rather than a PRG (see the full version for details [7]).

log2⁡|Σ|+O⁢(log3/2⁡n+log⁡n⋅log⁡w+log⁡n⋅log⁡(1/ε)).

For the complete details, see [7, Section 5]. The Cheng–Hoza reduction (Lemma 4.9 in [10]) is a recursive construction that uses randomness samplers at each step. Our construction is also recursive, but uses only the hypothesized PRG. We also note that compared to Theorem 3, the applies even when the hypothesized PRG has only O⁢(log⁡|Σ|) dependence on the alphabet size.

2 Proof Overview

In this section, we provide an informal overview of Theorem 1, and outline our alternative proof of the Cheng–Hoza result as given in Theorem 3. The reader may skip this part and proceed directly to the formal sections of the paper. Recall that this theorem takes a PRG for length-n, width-w BPs with error ε0=1/n and seed length s0, and produces a WPRG with error ε and seed length

s0+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w)

in the regime 1ε>w>n. When w<n (and more generally, for w=nO⁢(1)), the more involved step of our construction can be skipped, yielding a seed length s0+O⁢(log⁡1ε), and resulting in a significantly simpler construction.

The first component we need for proving Theorem 1 is a variant of the Richardson iteration, which we now turn to discuss.

2.1 Incremental and asymmetric Richardson iteration

The transformation underlying Theorem 1 uses the Richardson iteration, which is by now the standard tool for reducing the error of a PRG. However, our use of the Richardson iteration is more refined, and we begin by briefly describing it here (see Section 4.1 for the formal and complete treatment). For our purposes, the Richardson iteration – or rather, the variant of it used here – is an algorithm Rich that takes as input two WPRGs WL and WR for the same length n and width w, with corresponding errors εL and εR, and produces a new WPRG, denoted

Rich⁢(WL,WR),

with error guarantee εL⁢εR and seed length

sL+O⁢(log⁡1εL⁢εR).

In fact, both the error guarantee and the seed length are slightly more intricate (see Lemma 15), but for the purpose of this overview, it is best to suppress the exact dependence.

How our use of Richardson iteration differs.

There are several differences between our implementation of the Richardson iteration and those in the literature. While these distinctions provide useful context, the following discussion is primarily intended for experts; the reader may proceed with the proof overview without focusing on these differences.

In a nutshell, prior works apply the Richardson iteration to a single PRG using several correlated samples, taken with both positive and negative weights, to achieve error cancellation and thus obtain a lower error. The correlated seeds in these works are generated using an auxiliary PRG for BPs. In contrast, our approach reduces the error of two PRGs (and even WPRGs) which may be imbalanced in their error guarantees and seed lengths. The correlated seeds are obtained via extractors rather than PRGs, allowing for finer control over the seed length of the reduction, which is crucial in the presence of asymmetric WPRGs.

A second difference is our incremental application of the Richardson iteration: rather than applying it in a “one-shot” manner to achieve the desired error, we observe that it is preferable to invoke Richardson on just two instances and then compose the resulting procedure sufficiently many times. This approach is more economical, as the correlated seeds need not meet the final error guarantee from the start. Instead, the early iterations can operate with more coarsely correlated seeds.

Getting back to the proof overview of Theorem 1, the transformation proceeds in two phases:

  • ■

    Phase 1: Reduce the error from 1/n to 1/w.444Strictly speaking, we start with a slightly smaller error, e.g., 1/nc for some constant c>1. We ignore this technicality here.

  • ■

    Phase 2. Reduce the error from 1/w to the desired error ε.

2.2 Phase 1 – amplifying from inverse-length to inverse-width error

For the first phase – which is the more involved part, and can be skipped in the regime w=nO⁢(1), yielding a simpler construction. The key technical transformation is summarized in the following proposition (see Proposition 19 for the formal statement).

Proposition 4 (informal).

For any integer t≥1, a WPRG with error guarantee ε0<1/n and seed length s0 can be transformed into a WPRG with error ε=ε0t and seed length

s0+O⁢(t2⋅log⁡1ε0+log⁡w).

To be more precise, we assume a bound on the weights of the given WPRG as a function of the other parameters, in particular the error guarantee. This invariant, which we call error-dominated (see Definition 16), is preserved throughout our transformations, including the one given in Proposition 4. This ensures that the weights remain under control without the need to track them explicitly. In this informal overview, we will ignore them altogether.

The comb reduction.

The proof of Proposition 4 proceeds by applying the Richardson iteration recursively in a “comb-like” manner, as depicted in Figure 1 (which may explain the name).555Using a comb-like construction rather than a balanced binary tree allows us to exploit the asymmetry of the Richardson iteration described above. The “left loss” is the extractor’s seed length, whereas the “right loss” combines the extractor’s entropy loss with the entropy lost by revealing the program’s intermediate state. When w≫n, these losses differ substantially, and the comb lets the growing seed on the left absorb the larger loss on the right. A similar balancing appears already in [8]. More formally, given a WPRG W0 with error ε0 and seed length s0, we define a sequence of WPRGs W1,…,Wt−1 by setting, for each j≥1,

Wj=Rich⁢(Wj−1,W0).

It is easy to see that for each j≥1, the WPRG Wj has error guarantee εj=ε0j+1. Consequently, the seed length sj satisfies the recurrence

sj=sj−1+O⁢(log⁡1ε0j+1),

which readily yields the seed length bound stated in Proposition 4. The additive log⁡w term arises from a technical consideration that we suppress in this informal discussion.

Figure 1: Recursive “comb” structure.

Comb of combs.

Applying Proposition 4 with t=log⁡wlog⁡(1/ε0) yields a WPRG with the desired error ε, albeit with a seed length that has a quadratic dependence on log⁡w. To understand how this can be avoided, we first ask what error we can “buy” with an additive O⁢(log⁡w) term in the seed – a cost we are willing to incur. Since the seed length in Proposition 4 is s0+O⁢(t2⋅log⁡(1/ε0)), we can set

t=t1=log⁡wlog⁡(1/ε0),

thereby increasing the seed length by an additive O⁢(log⁡w) term over s0. The resulting error guaranteed by Proposition 4 is then ε1=ε0t1. Let us (re)denote the resulting WPRG by W1, which has seed length s1=s0+O⁢(log⁡w).

Generally, the error ε1 is not sufficiently small, and so we repeat the process and construct a new WPRG W2=𝖢𝗈𝗆𝖻t2⁢(W1) (hence the name “comb-of-combs”; see Figure 2 for an illustration.). Again, we wish to incur only an additive O⁢(log⁡w) increase in the seed length. Thus, we choose t2 so that t22⋅log⁡(1/ε1)=log⁡w, which yields

t2=(log⁡wlog⁡(1/ε0))1/4=t.

The resulting error is then ε2=ε0t1+12. Continuing in a recursive manner, we define Wj=𝖢𝗈𝗆𝖻tj⁢(Wj−1), with tj=tj−1. This results in error

εj=ε0t1+12+14+⋯+12j−1

using seed length s0+O⁢(j⋅log⁡w). Assuming now that ε0=1/n, a calculation shows that for ℓ=log⁡log⁡(log⁡wlog⁡n), the WPRG Wℓ achieves error 1/w and seed length s0+O⁢(ℓ⋅log⁡w), which is nearly linear in log⁡w, since ℓ is an extremely slowly growing function.

Figure 2: One level illustration of the comb of combs reduction.

2.3 Phase 2 – amplifying from inverse-width error

Once the error is below 1/w, or if we are already in the regime w=nO⁢(1), there is no further benefit to using asymmetric Richardson iteration, although the incremental approach remains advantageous. To obtain the final WPRG, we therefore compose the Richardson iterations in a binary-tree-like fashion, with the initial WPRG placed at the leaves. More precisely, let W0 denote the WPRG obtained in the previous sections, with error guarantee 1/w and seed length s0. We then define, for j=1,…,h=log⁡(log⁡(1/ε)log⁡w),

Wj=Rich⁢(Wj−1,Wj−1).

It is easy to verify that Wh achieves the desired error guarantee ε and has seed length

s0+2h⁢log⁡w=s0+O⁢(log⁡(1/ε)).

To wrap up, starting with a PRG with error 1/n and seed length s0, the overall seed length, accounting for both phases, is

s0+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w),

as claimed in Theorem 1. Moreover, note that in the regime w=nO⁢(1), only the second phase is invoked, yielding a seed length of s0+O⁢(log⁡1ε).

2.4 Improving Nisan’s PRG via optimal alphabet and error dependence

In this section, we give an overview of our alternative proof of the Cheng–Hoza reduction, as given in Theorem 3, showing that optimal dependence on the alphabet and error suffices to break the log-squared barrier. More precisely, recall that the goal here is to break the log-squared dependence on the length n in Nisan’s PRG, assuming the existence of a PRG with optimal alphabet and error dependence. Concretely, suppose we are given a PRG with seed length

log⁡|Σ|+O⁢(log2⁡n+log⁡n⋅log⁡w+log⁡1ε).

Our goal in proving Theorem 3 is to show that there exists an efficient transformation which then yields a PRG with seed length

log⁡|Σ|+O⁢(log3/2⁡n+log⁡n⋅log⁡w+log⁡n⋅log⁡1ε).

As we bear no news regarding the dependence on the width w, indeed, our construction exhibits the same log⁡n⋅log⁡w dependence as all previous constructions, we ignore the width parameter for simplicity.666Alternatively, the reader may think of the width w as a constant; recall that breaking the log-squared barrier remains open even for width w=4. Under this simplification, we assume the existence of a PRG with seed length log⁡|Σ|+O⁢(log2⁡n+log⁡1ε), and aim to construct a PRG with seed length log⁡|Σ|+O⁢(log3/2⁡n+log⁡n⋅log⁡1ε). The idea is to exploit the optimal dependence on Σ, as follows.

The PRG is constructed recursively with respect to the length n. Fix a parameter r (for the impatient reader, we note that we will take r=log⁡n), and let R=2r and t=log⁡nr. We construct a sequence of PRGs G0,G1,…,Gt, all for the same width w and alphabet Σ, where

Gj:{0,1}d⁢(j)→ΣRj.

Note that the final PRG Gt is for length-n BPs, and is the PRG produced by the transformation.

The first PRG, G0, is simply the identity function, so d⁢(0)=log2⁡|Σ|. For j≥1 we define Gj by composing R concatenated copies of Gj−1. The naive approach would be to define

Gj⁢(z)=Gj−1⁢(z1)∘Gj−1⁢(z2)∘⋯∘Gj−1⁢(zR),

where the seed z is partitioned into R disjoint blocks. But this results in an unacceptable blow-up in the seed length, d⁢(j)=R⋅d⁢(j−1), which ultimately yields a trivial PRG.

Instead, we use the hypothesized PRG to recycle the seeds of the R calls to Gj−1. In particular, let Hj denote the hypothesized PRG used to construct Gj. It has the form

Hj:{0,1}d⁢(j)→ΣjR,

where Σj={0,1}d⁢(j−1). With Hj in place, we define Gj via “sparsified folding”:777A similar length reduction step is also used in [12].

Gj⁢(z)=Gj−1⁢(Hj⁢(z)1)∘Gj−1⁢(Hj⁢(z)2)∘⋯∘Gj−1⁢(Hj⁢(z)R).

Note that Hj is a PRG with very large alphabet size, exponential in the seed length of Gj−1, yet its output length is only R, which we will take to be much smaller. It is at this point that we capitalize on the excellent dependence on the alphabet size. Indeed, by our hypothesis, the seed length of Hj satisfies

d⁢(j)=log⁡|Σj|⏟d⁢(j−1)+O⁢(r2+log⁡1εH),

where εH is the error parameter of Hj (taken uniformly across the j-s). Solving the recurrence yields

d⁢(t)=O⁢(t⋅(r2+log⁡1εH))+log⁡|Σ|.

In the full version [7], we prove that correlating the R seeds using a BP does indeed work, yielding a final error ε bounded by n⁢εH. This, together with our choice t=log⁡nr yields that the seed length is

d⁢(t)=O⁢(log⁡nr⋅(r2+log⁡n+log⁡1ε))+log⁡|Σ|.

Optimizing by setting r=log⁡n, we get the desired seed length.

3 Preliminaries

All logarithms in this paper are taken to base 2, unless otherwise stated. Whenever we write x∼A for A being a set, we mean that x is sampled uniformly at random from the flat distribution over A. We denote by Un the random variable distributed uniformly over {0,1}n.

We say f:Λ1→Λ2⋆ is explicit if it’s computable in time poly⁡(log⁡|Λ1|). We mostly do not keep precise track of the space complexity of our error-reduction procedure. A suitable bound follows from standard results on the space complexity of compositions, together with the space complexity of the underlying PRG whose error is being reduced.

3.1 Matrices, Branching Programs, and Space Complexity

A matrix is Boolean if all its entries are in {0,1}, and stochastic if all its entries are nonnegative and the sum of each column is 1. Denote by BSto⁢(w) the set of w×w boolean stochastic matrices. We will denote by ∥⋅∥ the induced ℓ1 norm, i.e., ‖A‖=maxj⁢∑i|Ai,j|.

We start by defining standard-order, read-once, branching programs.

Definition 5 (branching program).

Let Σ be some alphabet and let n,w∈ℕ. An (n,w,Σ) branching program (BP) is a sequence B=(B1,…,Bn), where each Bi:Σ→BSto⁢(w).

For i≤j we let Bi→j be the (j−i+1,Σ,w) BP (Bi,…,Bj).

Definition 6.

The value of an (n,w,Σ) BP B=(B1,…,Bn) on x=(x1,…,xn)∈Σn, denoted B⁢(x), is the realized w×w matrix of B when fed by x, i.e.,

B⁢(x)=Bn⁢(xn)⋅Bn−1⁢(xn−1)⁢⋯⁢B1⁢(x1).

If B is the empty sequence, we set ∅⁢(x)=Iw.

Definition 7 (weighted PRG).

We say (G,μ) is an (n,w,Σ,Γ,ε)-WPRG against BPs with seed length s if:

  • ■

    G:{0,1}s→Σn and μ:{0,1}s→ℝ,

  • ■

    For every (n,w,Σ) BP B=(B1,…,Bn), it holds that

    ‖𝔼x∼{0,1}s⁢[μ⁢(x)⋅B⁢(G⁢(x))]−𝔼x∼Σn⁢[B⁢(x)]‖≤ε,
  • ■

    For every x∈{0,1}s, |μ⁢(x)|≤Γ.

When μ≡1, the notion coincides with that of a PRG, in which case we omit the Γ from the tuple.

For 1≤i≤j≤n we let Gi→j:{0,1}s→Σj−i+1 be the corresponding truncation of G’s output. Note that if (G,μ) is an (n,w,Σ,Γ,ε) WPRG, then (Gi→j,μ) is an (j−i+1,w,Σ,Γ,ε) WPRG. We will often omit the subscript i→j when the length of the corresponding BP is clear from context.

3.2 Known PRG Constructions

Theorem 8 ([25]).

For any positive integers n, w, any error parameter ε>0 and any alphabet Σ, there exists an explicit (n,Σ,w,ε) PRG with seed length

s=log⁡|Σ|+O⁢(log⁡n⋅log⁡(n⁢wε)).

When w≫n, Armoni’s PRG [2] improves upon the INW generator. When instantiated with modern extractors, it works for all ranges of parameters [27], and has the optimal dependence on Σ [8].

Theorem 9 ([2, 27, 8]).

For any positive integers n, w, any error parameter ε>0 and any alphabet Σ, there exists an explicit (n,Σ,w,ε) PRG with seed length

s=log⁡|Σ|+O⁢(log⁡(n⁢w/ε)⁢log⁡nmax⁡(1,log⁡log⁡w−log⁡log⁡(n/ε))).

3.3 Seeded Extractors

The support of a random variable X distributed over some domain Ω is the set x∈Ω for which Pr⁡[X=x]≠0, which we denote by Supp⁢(X). The total variation distance (or, statistical distance) between two random variables X and Y over the same domain Ω is defined as |X−Y|=maxA⊆Ω⁡(Pr⁡[X∈A]−Pr⁡[Y∈A]). Whenever |X−Y|≤ε we say that X is ε-close to Y and denote it by X≈εY.

For a function f:Ω1→Ω2 and a random variable X distributed over Ω1, f⁢(X) is the random variable distributed over Ω2 obtained by choosing x according to X and computing f⁢(x). For a set A⊆Ω1, f⁢(A)={f⁢(x):x∈A}. For every f:Ω1→Ω2 and two random variables X and Y distributed over Ω1 it holds that |f⁢(X)−f⁢(Y)|≤|X−Y|, and this is often referred to as the data-processing inequality.

Definition 10 (min-entropy).

Let X be a discrete random variable over a set 𝒳. The min-entropy of X, denoted by H∞⁢(X), is defined as

H∞⁢(X)=minx∈𝒳⁡(−log⁡Pr⁡[X=x])=−log⁡(maxx∈𝒳⁡Pr⁡[X=x]). (1)
Definition 11 ((n,k) source).

An (n,k) source is a random variable X distributed over {0,1}n such that its min-entropy is at least k, i.e., H∞⁢(X)≥k. Equivalently, it is a distribution where for all x∈{0,1}n,

Pr⁡[X=x]≤2−k. (2)
Definition 12 (extractor).

A function 𝖤𝗑𝗍:{0,1}n×{0,1}d→{0,1}m is a (k,ε) (seeded) extractor if the following holds. For every (n,k) source X it holds that 𝖤𝗑𝗍⁢(X,Y)≈εUm, where Y is uniformly distributed over {0,1}d and is independent of X.

We will use two extractors, one in the balanced regime, and one in the unbalanced regime.

Theorem 13 ([21]).

There exists a constant c𝗌𝖾𝖾𝖽≥1 such that the following holds. For every positive integer n, and any Δ<n and ε>0, there exists an explicit (k=n−Δ,ε) extractor 𝖤𝗑𝗍:{0,1}n×{0,1}d→{0,1}n, where d=c𝗌𝖾𝖾𝖽⋅(Δ+log⁡(n/ε)).

Theorem 14 ([38, 6]).

There exist constants c𝗌𝖾𝖾𝖽,c𝗅𝗈𝗌𝗌≥1 such that the following holds. For every positive integer n, and any Δ<n and ε>0, there exists an explicit (k=n−Δ,ε) extractor 𝖤𝗑𝗍:{0,1}n×{0,1}d→{0,1}m, where d=c𝗌𝖾𝖾𝖽⋅log⁡(Δ/ε) and m=n−c𝗅𝗈𝗌𝗌⋅(Δ+log⁡1ε).

4 Our Error Reduction Procedure

In this section we prove Theorem 1 and deduce Corollary 2. We begin with an informal overview of the Richardson iteration technique. This procedure depends on a parameter k that governs the quality of error reduction: roughly, an error-ε PRG is transformed into an error-εk WPRG. As discussed in the proof overview, in this work we observe that it is more economical to work with k=2 and then compose the resulting WPRGs.

Our use of the Richardson iteration is asymmetric. In particular, in our error reduction we apply the iteration to WPRGs with varying error parameters. To set the stage, we first review, at an informal level, the Richardson iteration with parameter k=2 in the symmetric setting. With this intuition in place, we then proceed in Section 4.1 to formally construct the Richardson iteration with parameter k=2 for the asymmetric case.

Suppose we are given

  • ■

    w×w sub-stochastic matrices M1,…,Mn, and,

  • ■

    Crude approximations M~i,j to Mi⁢Mi−1⁢⋯⁢Mj for all 1≤j<i≤n ( for j=i we naturally take M~i,i=Mi).

In the context of space bounded derandomization, [32] describe a method to use M1,…,Mn to refine the crude approximations to much better approximations. First, they “plant” the matrix product problem within a matrix inversion problem. Specifically, they form the (n+1)×(n+1) block matrix

M=(000⋯00M100⋯000M20⋱⋮⋮⋮⋮⋱⋱0000⋯Mn−10000⋯0Mn0) (3)

and define L=I−M. Then they observe that the inverse of L is:

(L−1)i,j={Mi−1⁢⋯⁢Mjif ⁢i>j,Iif ⁢i=j,0otherwise.

Thus, the product we wish to approximate is a block within L−1. We can use the crude approximations M~i−1,j to form the matrix

L−1~i,j={M~i−1,j,if ⁢i>j,I,if ⁢i=j,0,if ⁢i<j.

and L−1~ is a crude approximation to L−1. Prior works apply Richardson iteration to get a better approximation to L−1. Specifically they take

L−1~^ =2⁢L−1~−L−1~⁢L⁢L−1~, (4)

and it is immediate to check that

‖I−L⁢L−1~^‖=‖I−L⁢L−1~‖2.

Thus, L−1~^ yields a quadratically improved approximation of L−1 and therefore also of M1⋅…⋅Mn. An explicit formula for the approximation of M1⋅…⋅Mn can be derived: For every n≥3,

M~^n+1,1 =∑r=1n−2M~n,r+2⁢Mr+1⁢M~r,1−∑r=1n−3M~n,r+2⁢M~r+1,1. (5)

For example, for n=4, the approximation of M4⁢M3⁢M2⁢M1 is

M~^5,1=M~4,3⁢M2⁢M1+M4⁢M3⁢M~2,1−M~4,3⁢M~2,1.

Observe that Equation 5 is expressed as the difference of two sums. In the first (positive) sum, each summand is a product of three terms – two given approximations with an input matrix Mr sandwiched in the middle. In the second (negative) sum, the product omits this middle input matrix.

[36] and [14] independently notice that if the approximations M~ are obtained with a PRG, then the approximation M~^ can be realized with a WPRG 888The use of weights here is essential, as some of terms in Equation 5 come with a negative weight.. A naive (and expensive) implementation of this would construct the WPRG for M~^ using two independent calls to the WPRGs for M~. A better idea is to recycle the seeds needed for the two calls to the WPRG of M~. In this work we explore what happens when we employ two different WPRGs, each with a different accuracy level, and we show that this leads to better WPRGs.

4.1 Asymmetric Richardson Iteration

In this section we make the above idea precise.

Construction.

We are given two WPRGs, which we think of as a “left” WPRG and a “right” one, possibly with different parameters, and an extractor.

  • ■

    An (n,w,Σ,ΓL,εL) WPRG (GL,μL) with seed length sL.

  • ■

    An (n,w,Σ,ΓR,εR) WPRG (GR,μR) with seed length sR.

  • ■

    A (k,ε𝖤𝗑𝗍) extractor 𝖤𝗑𝗍:{0,1}sL×{0,1}d𝖤𝗑𝗍→{0,1}sR, where k=sL−log⁡wε𝖤𝗑𝗍.

The construction of our new WPRG

Rich𝖤𝗑𝗍⁢((GL,μL),(GR,μR))=(G,μ)

goes as follows. We interpret the set of seeds S as [2⁢n−5]×{0,1}sL×{0,1}d𝖤𝗑𝗍×{0,1}d𝖤𝗑𝗍. Given (t,xL,y1,y2)∈S, we set t′=t−n+2, and define

G⁢(t,xL,y1,y2) ={G1→tL⁢(xL)∘𝖤𝗑𝗍⁢(xL,y2)[1,log⁡|Σ|]∘Gt+2→nR⁢(𝖤𝗑𝗍⁢(xL,y1))if ⁢t≤n−2,G1→t′+1L⁢(xL)∘Gt′+2→nR⁢(𝖤𝗑𝗍⁢(xL,y1))otherwise.
μ⁢(t,xL,y1,y2) =(2⁢n−5)⋅{μL⁢(xL)⋅μR⁢(𝖤𝗑𝗍⁢(xL,y1))if ⁢t≤n−2,−μL⁢(xL)⋅μR⁢(𝖤𝗑𝗍⁢(xL,y1))otherwise.

Note that the construction exactly corresponds to Equation 5, where we use two different WPRGs for approximating the matrices. Notice that the first n−2 terms come with a positive sign, and the last n−3 terms with a negative sign.

Lemma 15.

Given (GL,μL), (GR,μR), and 𝖤𝗑𝗍 as above, it holds that (G,μ) is an (n,w,Σ,Γ,ε) WPRG, where:

  • ■

    The seed length s=log⁡|S| satisfies s=log⁡(2⁢n−5)+sL+2⁢d𝖤𝗑𝗍,

  • ■

    The weight of G is at most Γ=c⋅n⁢ΓL⁢ΓR for some constant c≥1, and,

  • ■

    The error ε is bounded by ε≤4⁢(n+1)2⁢εL⁢εR+Γ⋅ε𝖤𝗑𝗍.

Proof.

The weighted generator (G,μ) treats each seed as a quadruple (t,xL,y1,y2). Here t∈[2⁢n−5] specifies which of the (n−2) “positive” or (n−3) “negative” summands in the Richardson expansion is selected; xL∈{0,1}sL is drawn according to μL; and y1,y2∈{0,1}d𝖤𝗑𝗍 are independent extractor seeds. Encoding t requires log⁡(2⁢n−5) bits, xL requires sL bits, and the two extractor seeds contribute 2⁢d𝖤𝗑𝗍 bits in total, giving a seed length of

s=log⁡(2⁢n−5)+sL+2⁢d𝖤𝗑𝗍.

Each output of (G,μ) has weight

μ⁢(t,xL,y1,y2)=±(2⁢n−5)⁢μL⁢(xL)⁢μR⁢(𝖤𝗑𝗍⁢(xL,y1)),

and therefore satisfies

|μ⁢(t,xL,y1,y2)|≤(2⁢n−5)⁢ΓL⁢ΓR.

We move to analyzing the error of the weighted PRG.

Constructing approximate inverses.

Let B be an (n,w,Σ) BP with transition matrices M1,…,Mn. Let L be the corresponding (n+1)⁢w×(n+1)⁢w block matrix defined in Equation 3 whose inverse L−1 encodes all partial products Mi⁢⋯⁢Mj+1. We form two approximate inverses L−1⁢(L) and L−1⁢(R) by replacing each block Mi,j with

M~i,j(L)=𝔼x∼{0,1}sL⁢[μL⁢(x)⋅Bi→j⁢(GL⁢(x))]orM~i,j(R)=𝔼x∼{0,1}sR⁢[μR⁢(x)⋅Bi→j⁢(GR⁢(x))],

respectively. Recalling that (GL,μL) and (GR,μR) have errors εL and εR, we have

‖Mi,j−M~i,j(L)‖≤εL,‖Mi,j−M~i,j(R)‖≤εR.

Summing these errors over the n+1 block rows gives

‖L−1−L−1⁢(L)‖≤(n+1)⁢εL,‖L−1−L−1⁢(R)‖≤(n+1)⁢εR.

As ‖L‖≤2,

‖I−L−1⁢(L)⁢L‖≤ 2⁢(n+1)⁢εL,‖I−L−1⁢(R)⁢L‖≤ 2⁢(n+1)⁢εR.

Asymmetric Richardson.

“Vanilla” Richardson refines a single crude inverse A≈L−1 via

A⟼2⁢A−A⁢L⁢A,

which satisfies ‖I−(2⁢A−A⁢L⁢A)⁢L‖=‖I−A⁢L‖2. In principle, introducing two approximations looks unnecessary–one could just reuse the more accurate one. In our setting, however, the two appearances of L−1~ are generated from different seeds: the left term is driven by xL, while the right term is obtained from xL through an extractor and therefore may have different accuracy. This asymmetry naturally leads us to use a Richardson-type update that mixes two approximations,

R=L−1⁢(L)+L−1⁢(R)−L−1⁢(L)⁢L⁢L−1⁢(R).

A short calculation shows that

I−R⁢L=(I−L−1⁢(L)⁢L)⁢(I−L−1⁢(R)⁢L).

Consequently,

‖I−R⁢L‖≤‖I−L−1⁢(L)⁢L‖⁢‖I−L−1⁢(R)⁢L‖≤4⁢(n+1)2⁢εL⁢εR,

and in particular the bottom-left block satisfies

∥|R[n+1,1]−Mn⋯M1∥≤4(n+1)2εLεR.

Uncorrelated seeds.

Assume that the seed xR for GR and the symbol σ∈Σ are sampled independently from xL and uniformly. Given t∈[2⁢n−5], we consider the above two cases. When t∈[n−2], letting r=t, the generator outputs G1→rL⁢(xL)∘σ∘Gr+2→nR⁢(xR). Then,

𝔼xL,xR,σ⁢[μL⁢(xL)⁢μR⁢(xR)⁢B⁢(G1→rL⁢(xL)∘σ∘Gr+2→nR⁢(xR))]=M~n,r+2(R)⁢Mr+1⁢M~r,1(L).

When t>n−2, we denote r to be such that t=n−2+r, and now

𝔼xL,xR⁢[μL⁢(xL)⁢μR⁢(xR)⁢B⁢(G1→r+1L⁢(xL)∘Gr+2→nR⁢(xR))]=−M~n,r+2(R)⁢M~r+1,1(L).

Averaging over t∈[2⁢n−5] and multiplying by 2⁢n−5 yields exactly

∑r=1n−2M~n,r+2(L)⁢Mr+1⁢M~r,1(R)−∑r=1n−3M~n,r+2(L)⁢M~r+1,1(R),

which is the (n+1,1)-block of the Richardson matrix R. Thus, when xR and σ are drawn independently, the weighted generator’s output matches R⁢[n+1,1].

Correlating 𝒙𝑹 and 𝝈 with 𝒙𝑳 via two extractor calls.

We now replace the independent choices (xR,σ) by

xR=𝖤𝗑𝗍⁢(xL,y1)∈{0,1}sR,σ=𝖤𝗑𝗍⁢(xL,y2)[1,log⁡|Σ|]∈Σ,

where y1,y2 are independent uniform seeds (and independent of xL). We bound the difference in the ℓ1 norm of the (n+1,1)-block contribution.

We use the standard seed-recycling argument for width-w ROBPs. Conditioning on reaching the state q∈[w] after reading xL reveals at most, roughly, log⁡w bits of information; Formally, except with probability at most ε𝖤𝗑𝗍, this conditioning reduces the min-entropy of the left seed by at most log⁡(w/ε𝖤𝗑𝗍). Setting Δ:=log⁡(w/ε𝖤𝗑𝗍), and using our extractor 𝖤𝗑𝗍:{0,1}sL×{0,1}d𝖤𝗑𝗍→{0,1}sR with entropy loss Δ and error ε𝖤𝗑𝗍, the condition

sL−Δ≥sL−log⁡wε𝖤𝗑𝗍=k

guarantees that 𝖤𝗑𝗍⁢(xL,U) is ε𝖤𝗑𝗍-close to uniform even after conditioning on q. Consequently, for any functions fL,fR,

‖𝔼xL,y⁢[B⁢(fL⁢(xL)∘fR⁢(𝖤𝗑𝗍⁢(xL,y)))]−𝔼xL,xR⁢[B⁢(fL⁢(xL)∘fR⁢(xR))]‖≤2⁢ε𝖤𝗑𝗍.

Taking the weights into account, recalling that |μL|≤ΓL and |μR|≤ΓR, we have
∥𝔼xL,y[(2n−5)μL(xL)μR(𝖤𝗑𝗍(xL,y))⋅B(fL(xL)∘fR(𝖤𝗑𝗍(xL,y)))] −𝔼xL,xR[(2n−5)μL(xL)μR(xR)⋅B(fL(xL)∘fR(xR))]∥≤c⋅(2n−5)ΓLΓRε𝖤𝗑𝗍

for some constant c≥1. The ultimate error bound is obtained by the triangle inequality. ◀

To conclude this section, we define a useful invariant which will be helpful towards establishing our WPRG.

Definition 16.

We say that an (n,w,Σ,Γ,ε) WPRG is error-dominated if

Γ≤1c⁢(n+1)3⁢ε,

where c is the same constant from Lemma 15.

Note that error-dominated WPRGs necessarily have low error. We record the following observation.

Claim 17.

Keeping the notation above, particularly the constant c from Lemma 15, assume that both (GL,μL) and (GR,μR) are error-dominated, and that

ε𝖤𝗑𝗍≤n2⁢εL⁢εRc⁢Γ.

Then, (G,μ) is error-dominated.

Proof.

By Lemma 15, the composed generator satisfies

Γ=c⁢n⁢ΓL⁢ΓRandε≤4⁢(n+1)2⁢εL⁢εR+Γ⁢ε𝖤𝗑𝗍.

Using ε𝖤𝗑𝗍≤n⁢εL⁢εRc⁢Γ, we get

ε≤(4⁢(n+1)2+n2)⁢εL⁢εR≤5⁢(n+1)2⁢εL⁢εR.

Since (GL,μL) and (GR,μR) are error-dominated,

ΓL≤1c⁢(n+1)3⁢εLandΓR≤1c⁢(n+1)3⁢εR.

Therefore,

Γ≤c⁢n⁢ΓL⁢ΓR≤c⁢nc2⁢(n+1)6⋅1εL⁢εR≤c⁢nc2⁢(n+1)6⋅5⁢(n+1)2ε=nc⁢(n+1)4⋅1ε≤1c⁢(n+1)3⁢ε.

⊲

4.2 A Comb Reduction

In this section we define a comb-like construction, that composes our asymmetric Richardson construction given in Section 4.1 as follows. For some base (error-dominated) WPRG W0, and a sequence of extractors 𝖤𝗑𝗍1,…,𝖤𝗑𝗍t, we define Wi recursively as

Wi=Rich𝖤𝗑𝗍i⁢(Wi−1,W0).

We denote by W0=(G0,μ0) our (n,w,Σ,Γ0,ε0) error-dominated WPRG, and by s0 its seed length. We proceed to set the parameters of our extractors, each of the t extractors

𝖤𝗑𝗍i:{0,1}s⁢(i)×{0,1}d⁢(i)→{0,1}s0

is given in Theorem 14 and set to have error ε𝖤𝗑𝗍⁢(i), where the ε𝖤𝗑𝗍⁢(i)’s are as follows. Define, for each i∈[t], ε⁢(i)=(5⁢(n+1)2⁢ε0)i⁢ε0. Note that the sequence of ε⁢(i)-s satisfy ε⁢(i)=5⁢(n+1)2⁢ε⁢(i−1)⋅ε0. For each i∈[t] set

ε𝖤𝗑𝗍⁢(i)=n2⁢ε0c⁢Γ⁢(i)⋅ε⁢(i−1),

where Γ⁢(i)=(c⁢n⁢Γ0)i⁢Γ0. Note that the Γ⁢(i)-s satisfy the recurrence relation Γ⁢(i)=c⁢n⁢Γ⁢(i−1)⁢Γ0.

By Lemma 15, the input lengths satisfy s⁢(1)=s0+c𝗌𝖾𝖾𝖽⁢log⁡(w/ε𝖤𝗑𝗍⁢(1)), and for each 2≤i≤t,

s⁢(i+1)=s⁢(i)+2⁢c𝗌𝖾𝖾𝖽⁢log⁡(log⁡w/ε𝖤𝗑𝗍⁢(i+1))+log⁡(2⁢n−5).

We record that:

Claim 18.

For every i∈[t] it holds that

log⁡1ε𝖤𝗑𝗍⁢(i)=O⁢(i⁢log⁡n⁢Γ0ε0),
s⁢(i)=s0+O⁢(log⁡w+i2⁢log⁡n⁢Γ0ε0),

and

d⁢(i)=O⁢(log⁡log⁡w+i⁢log⁡n⁢Γ0ε0).

Proof.

By definition of ε𝖤𝗑𝗍⁢(i) and error domination from Claim 17:

ε𝖤𝗑𝗍⁢(i)=ε⁢(i−1)⁢ε0⁢n2c⁢Γ⁢(i)≥1c⋅ε⁢(i−1)⁢ε0⁢n2⋅c⁢(n+1)3⁢ε⁢(i)=(n+1)⁢n2⁢ε⁢(i)25,

so

log⁡1ε𝖤𝗑𝗍⁢(i)=O⁢(i⋅log⁡n⁢Γ0ε0).

For the WPRG’s seed length, we have

s⁢(i) =s0+s⁢(1)+(i−1)⋅log⁡(2⁢n−5)+2⁢c𝗌𝖾𝖾𝖽⁢∑k=2ilog⁡log⁡wε𝖤𝗑𝗍⁢(k+1)
=s0+O⁢(log⁡w+i⁢log⁡log⁡w+i2⁢log⁡n⁢Γ0ε0).

By the construction given in Section 4.1, the entropy loss of each extractor is Δ⁢(i)=log⁡(w/ε𝖤𝗑𝗍⁢(i)). Thus, we can indeed output s0 bits as

s⁢(i)≥s0+c𝗅𝗈𝗌𝗌⁢(Δ⁢(i)+log⁡1ε𝖤𝗑𝗍⁢(i)).

We thus get that

d⁢(i)=O⁢(log⁡log⁡w+log⁡1ε𝖤𝗑𝗍⁢(i))=O⁢(log⁡log⁡w+i⁢log⁡n⁢Γ0ε0).

⊲

We denote this section’s transformation, which on input W0 construct Wt, as 𝖢𝗈𝗆𝖻t⁢(W0). The parameters of the construction are summarized in the following theorem, whose proof readily follows from Lemma 15, Claim 17, and Claim 18.

Proposition 19.

Keeping the above notation, assuming ε0≤1/n5 and that s0≥log⁡|Σ|+Ω⁢(log⁡(w/ε0)), 𝖢𝗈𝗆𝖻t⁢(W0) is an error-dominated (n,w,Σ,Γt,εt) WPRG with seed length

s0+O⁢(t2⁢log⁡1ε0+log⁡w),

and error εt=ε0t/2.

We emphasize that error domination of the WPRG is preserved, and moreover, that if W0 is explicit, Wt is explicit as well.

4.3 Amplifying from Inverse-Length to Inverse-Width Error

To reduce the error from n−Ω⁢(1) to w−Ω⁢(1), we define a “comb-of-combs” construction as follows. Letting W0 be an error dominated (n,w,Σ,Γ0,ε0) WPRG that satisfies the assumptions of Proposition 19, for some t1,…,tℓ, we define the sequence of WPRGs defined by

Wi=𝖢𝗈𝗆𝖻ti⁢(Wi−1),

and set 𝖢𝗈𝖢t1,…,tℓ⁢(W0)=Wℓ.

Concretely, we start with ε0=1/n5, choose

ℓ=log⁡log⁡(log⁡wlog⁡n),

and for each i∈[ℓ], we take

ti=2⁢(log⁡wlog⁡n)2−i.

Under this choice of parameters, 𝖢𝗈𝖢t1,…,tℓ⁢(W0) satisfies the following.

Proposition 20.

Keeping the above notation,

𝖢𝗈𝖢t1,…,tℓ⁢(W0)

is an explicit error-dominated (n,w,Σ,Γ,ε) WPRG with ε=1/w, seed length s0+O⁢(ℓ⁢log⁡w).

Proof.

First, note that the fact that Wℓ is error dominated already follows from Proposition 19, and we proceed to analyzing the error. Letting εi be the error of Wi, by Proposition 19 we know that εi=εi−1ti/2. By our choice of ti-s, denoting r=log⁡wlog⁡n, we get that

εℓ=ε02−ℓ⁢∏i∈[ℓ]ti=ε0∏i∈[ℓ]r2−i=ε0r1−2−ℓ.

Now, 2ℓ=log⁡r, so r1−2−ℓ=r/2. Recalling that ε0=n−5, we get ε0r/2=n−5⁢r/2≤1/w.

For the seed length, denote by si the seed length of Wi. By Proposition 19, we know that each si=si−1+O⁢(ti2⁢log⁡(1/εi−1)). Fixing some i∈[ℓ], note from the above that

ti2⋅log⁡1εi−1=ti2⋅r1−2−(i−1)⁢log⁡1ε0=4⁢r2−i+1⋅r1−2−i+1⁢log⁡1ε0=20⁢log⁡n⋅r=20⁢log⁡w.

Thus, si=si−1+O⁢(log⁡w) and we’re done with the seed length caclculation. Finally, note that in order to invoke Proposition 19, we need to make sure that si≥log⁡|Σ|+Ω⁢(log⁡(w/εi)), which follows from the fact that ti2⁢log⁡(1/εi−1)=Ω⁢(log⁡(1/εi)) and that s0≥log⁡|Σ|+Ω⁢(log⁡w). ◀

4.4 Amplifying to an Arbitrary Error

Once we achieved an error of 1/w, we reduce the error to an arbitrary desired error ε by recursively applying the Richardson iteration on the same WPRG, i.e., at the base of the recursion we use 𝖢𝗈𝖢 above on the given base-WPRG W. More formally, we start with V0=𝖢𝗈𝖢t1,…,tℓ⁢(W) as above, set

h=log⁡(log⁡(1/ε)log⁡(w/6⁢n2)),

and for each i∈[h], define

Vi=Rich𝖤𝗑𝗍i⁢(Vi−1,Vi−1),

where the extractors 𝖤𝗑𝗍1,…,𝖤𝗑𝗍h are defined as follows. We denote the seed length of each (n,w,Σ,Γi,εi) WPRG Vi by si, and the seed length of W by s⁢(W). Each

𝖤𝗑𝗍i:{0,1}si−1×{0,1}di→{0,1}si−1

is taken to be the (ki,ε𝖤𝗑𝗍i) extractor of Theorem 13 as in Section 4.2, where ki=si−1−log⁡(w/ε𝖤𝗑𝗍i), and ε𝖤𝗑𝗍i=n2⁢εi−12c⁢Γi. By Lemma 15, we have the recurrence relation relating the seed lengths of the WPRGs

si=si−1+2⁢di+O⁢(log⁡n)=si−1+O⁢(log⁡(1/ε𝖤𝗑𝗍i)),

and the recursive relation of the errors is εi≤6⁢n2⁢εi−12. Solving for the recursion, recalling ε0=1/w, we get

εi≤(6⁢n2w)2i.

Our choice of h guarantees a final error of εh≤ε.

By Theorem 13, the seed length

di=O⁢(log⁡(w/ε𝖤𝗑𝗍i))=O⁢(log⁡(1/εi))=O⁢(2i⁢log⁡w),

and so the recurrence simplifies to si=si−1+O⁢(2i⁢log⁡w), yielding

sh=s0+O⁢(2h⁢log⁡w)=s0+O⁢(log⁡(1/ε)).

By Proposition 20,

s0=s⁢(W)+O⁢(log⁡log⁡(log⁡wlog⁡n)⋅log⁡w),

and so the final seed length is

sh=s⁢(W)+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w).

We summarize this in the following theorem, which is the formal version of Theorem 1 whose proof follows by the above calculations, also noting that the constructed WPRGs remain error-dominated and explicit.

Theorem 21.

Keeping the above notation, let W be an explicit error-dominated(n,w,Σ,Γ0,ε0=1/n5) WPRG with seed length s⁢(W). Then, Vh is an error-dominated (n,w,Σ,Γ,ε) WPRG with seed length

s⁢(W)+O⁢(log⁡1ε+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w).

Finally, for our base-WPRG we’ll choose Armoni’s explicit PRG from Theorem 9.

Corollary 22.

For any positive integers n,w such that w>n, any ε>0, and any alphabet Σ, there exists an explicit (n,w,Σ,Γ,ε) WPRG with seed length

log⁡|Σ|+O⁢(log2⁡n+log⁡n⋅log⁡wlog⁡log⁡w−log⁡log⁡n+log⁡log⁡(log⁡wlog⁡n)⋅log⁡w+log⁡1ε).

and Γ≤max⁡{1,1poly⁡(n)⋅ε}. In particular, when w=2nα for some constant α∈(0,1), the seed length above becomes

log⁡|Σ|+O⁢((log⁡log⁡log⁡w)⋅log⁡w+log⁡1ε).

When w is only polynomial in n, we can perform the error reduction step of Section 4.4 directly, and for the base-PRG, we can use the simpler INW generator (see Theorem 8) and get the following corollary.

Corollary 23.

For any positive integers n,w such that w=nO⁢(1), any ε>0, and any alphabet Σ, there exists an explicit (n,w,Σ,Γ,ε) WPRG with seed length

log⁡|Σ|+O⁢(log2⁡n+log⁡1ε)

and Γ≤max⁡{1,1poly⁡(n)⋅ε}.

References

  • [1] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In Annual Symposium on Foundations of Computer (FOCS), pages 218–223. IEEE, 1979.
  • [2] Roy Armoni. On the derandomization of space-bounded computations. In International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), volume 1518 of LNCS, pages 47–59. Springer, 1998. doi:10.1007/3-540-49543-6_5.
  • [3] Allan Borodin, Stephen Cook, and Nicholas Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58(1-3):113–136, 1983. doi:10.1016/S0019-9958(83)80060-6.
  • [4] Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 49(5):STOC18–242–STOC18–299, 2020. doi:10.1137/18M1197734.
  • [5] Mark Braverman, Anup Rao, Ran Raz, and Amir Yehudayoff. Pseudorandom generators for regular branching programs. SIAM Journal on Computing, 43(3):973–986, 2014. doi:10.1137/120875673.
  • [6] Eshan Chattopadhyay and Jyun-Jie Liao. Optimal error pseudodistributions for read-once branching programs. In Computational Complexity Conference (CCC), pages 25:1–25:27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPIcs.CCC.2020.25.
  • [7] Ben Chen, Gil Cohen, Dean Doron, Yuval Khaskelberg, and Amnon Ta-Shma. Improved error reduction for weighted PRGs. In Electronic Colloquium on Computational Complexity (ECCC), 2026. Manuscript.
  • [8] Ben Chen and Amnon Ta-Shma. Simplifying Armoni’s PRG. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 36:1–36:8. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.APPROX/RANDOM.2025.36.
  • [9] Lijie Chen, William M. Hoza, Xin Lyu, Avishay Tal, and Hongxun Wu. Weighted pseudorandom generators via inverse analysis of random walks and shortcutting. In Annual Symposium on Foundations of Computer Science (FOCS), pages 1224–1239. IEEE, 2023. doi:10.1109/FOCS57990.2023.00072.
  • [10] Kuan Cheng and William M. Hoza. Hitting sets give two-sided derandomization of small space. Theory of Computing, 18(21):1–32, 2022. doi:10.4086/toc.2022.v018a021.
  • [11] Kuan Cheng and Yichuan Wang. BPL ⊆ L-AC1. In 39th Computational Complexity Conference (CCC 2024), volume 300 of Leibniz International Proceedings in Informatics (LIPIcs), pages 32:1–32:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPIcs.CCC.2024.32.
  • [12] Kuan Cheng and Ruiyang Wu. Weighted pseudorandom generators for read-once branching programs via weighted pseudorandom reductions. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3423–3458. SIAM, 2026. doi:10.1137/1.9781611978971.124.
  • [13] Gil Cohen, Dean Doron, Tomer Manket, Edward Pyne, Yichuan Wang, and Tal Yankovitz. A study of error reduction polynomials. In Electronic Colloquium on Computational Complexity (ECCC), 2025. Manuscript.
  • [14] Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error reduction for weighted PRGs against read once branching programs. In Computational Complexity Conference (CCC), pages 22:1–22:17. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.22.
  • [15] Gil Cohen, Dean Doron, Ori Sberlo, and Amnon Ta-Shma. Approximating iterated multiplication of stochastic matrices in small space. In Annual Symposium on Theory of Computing (STOC), pages 35–45. ACM, 2023. doi:10.1145/3564246.3585181.
  • [16] Anindya De. Pseudorandomness for permutation and regular branching programs. In Computational Complexity Conference (CCC), pages 221–231. IEEE, 2011. doi:10.1109/CCC.2011.23.
  • [17] Dean Doron, Pooya Hatami, and William M. Hoza. Near-optimal pseudorandom generators for constant-depth read-once formulas. In 34th Computational Complexity Conference (CCC 2019), pages 16:1–16:34. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.CCC.2019.16.
  • [18] Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, and Salil Vadhan. Pseudorandom generators for read-once monotone branching programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 58:1–58:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.58.
  • [19] Dean Doron, Edward Pyne, and Roei Tell. Opening up the distinguisher: A hardness to randomness approach 𝐁𝐏𝐋=𝐋 that uses properties of 𝐁𝐏𝐋. In Annual Symposium on Theory of Computing (STOC), pages 2039–2049. ACM, 2024.
  • [20] Dean Doron and Roei Tell. Derandomization with Minimal Memory Footprint. In 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs), pages 11:1–11:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.CCC.2023.11.
  • [21] Oded Goldreich and Avi Wigderson. Tiny families of functions with random properties: A quality-size trade-off for hashing. Random Struct. Algorithms, 11(4):315–343, 1997. doi:10.1002/(SICI)1098-2418(199712)11:4\%3C315::AID-RSA3\%3E3.0.CO;2-1.
  • [22] William M. Hoza. Better pseudodistributions and derandomization for space-bounded computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM), pages 28:1–28:23. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.APPROX/RANDOM.2021.28.
  • [23] William M. Hoza, Edward Pyne, and Salil Vadhan. Pseudorandom generators for unbounded-width permutation branching programs. In Innovations in Theoretical Computer Science Conference (ITCS), pages 7:1–7:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ITCS.2021.7.
  • [24] William M. Hoza and David Zuckerman. Simple optimal hitting sets for small-success 𝐑𝐋. SIAM Journal on Computing, 49(4):811–820, 2020. doi:10.1137/19M1268707.
  • [25] Russell Impagliazzo, Noam Nisan, and Avi Wigderson. Pseudorandomness for network algorithms. In Annual Symposium on Theory of Computing (STOC), pages 356–364. ACM, 1994. doi:10.1145/195058.195190.
  • [26] H. Jung. Relationships between probabilistic and deterministic tape complexity. In Mathematical Foundations of Computer Science (MFCS), volume 118 of LNCS, pages 339–346. Springer, 1981. doi:10.1007/3-540-10856-4_101.
  • [27] Daniel M. Kane, Jelani Nelson, and David P. Woodruff. Revisiting norm estimation in data streams. arXiv preprint arXiv:0811.3648, 2008. arXiv:0811.3648.
  • [28] Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501–1526, 2002. doi:10.1137/S0097539700389652.
  • [29] Michal Kouckỳ, Prajakta Nimbhorkar, and Pavel Pudlák. Pseudorandom generators for group products. In Annual Symposium on Theory of Computing (STOC), pages 263–272. ACM, 2011.
  • [30] Daniel Kozlov. Simplifying the BCG PRPD for space bounded computation. Master’s thesis, Tel-Aviv University, 2020. Available at https://www.cs.tau.ac.il/˜amnon/Students/daniel.kozlov.pdf.
  • [31] Raghu Meka, Omer Reingold, and Avishay Tal. Pseudorandom generators for width-3 branching programs. In Annual Symposium on Theory of Computing (STOC), pages 626–637. ACM, 2019. doi:10.1145/3313276.3316319.
  • [32] Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space. In Annual Symposium on the Foundations of Computer Science (FOCS), pages 801–812. IEEE, 2017. doi:10.1109/FOCS.2017.79.
  • [33] Noam Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449–461, 1992. doi:10.1007/BF01305237.
  • [34] Noam Nisan and David Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996. doi:10.1006/JCSS.1996.0004.
  • [35] Aaron Putterman and Edward Pyne. Near-optimal derandomization of medium-width branching programs. In Annual Symposium on Theory of Computing (STOC), pages 23–34. ACM, 2023.
  • [36] Edward Pyne and Salil Vadhan. Pseudodistributions That Beat All Pseudorandom Generators. In 36th Computational Complexity Conference (CCC 2021), volume 200 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.CCC.2021.33.
  • [37] Ran Raz and Omer Reingold. On recycling the randomness of states in space bounded computation. In 31st Annual Symposium on Theory of Computing (STOC 1999), pages 159–168. ACM, 1999. doi:10.1145/301250.301294.
  • [38] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of Mathematics, pages 157–187, 2002.
  • [39] Michael E. Saks and Shiyu Zhou. 𝐁𝐏𝐇⁢𝐒𝐏𝐀𝐂𝐄⁢(S)⊆𝐃𝐒𝐏𝐀𝐂𝐄⁢(S2/3). Journal of Computer and System Sciences, 58(2):376–403, 1999.
  • [40] Walter J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2):177–192, 1970. doi:10.1016/S0022-0000(70)80006-X.