Introduction

One central question in complexity theory is whether randomness is necessary for e cient computation. In the time setting, the question is essentially asking whether P = BPP. While it is commonly believed that P = BPP [23,16], it is known that establishing this would imply breakthrough lower bounds in complexity theory [13,17], which seems to be out of reach for current techniques. Therefore, most previous works are devoted to derandomizing sub-classes of BPP. In particular, the class of randomized log-space algorithms (BPL) has attracted a lot of attention, since not only it contains many interesting problems, but also it is indeed possible to give unconditional derandomizations of BPL [22,27].

A leading approach to derandomize BPL is to construct explicit PRGs for ordered read-once branching programs (see below for a formal definition) with short seed length.

I Definition 1. An ordered read-once branching program (roBP) B of length n and width w computes a function B : {0, 1} n ae {0, 1}. The program has (n + 1) layers of states

where V i contains all states in the i-th layer. Being width-w means that |V i | AE w for every i oe [n]. On an input x oe {0, 1} n , the branching program computes as follows. It starts at a fixed start state s oe V 0 . Then for every i = 1, 2, . . . , n, it reads the next input bit x i and updates its state according to a transition function B i : V i≠1 ◊ {0, 1} ae V i by taking v i = B t (v i≠1 , x i ). Note that the transition function B i can di er at each time step.

When we use the program to compute a decision problem, we specify a set V acc ™ [w] of accepting states in the final layer. Let v n be the final state reached by the branching program on input x. If v n oe V acc , the branching program accepts, denoted by B(x) = 1. Otherwise, the program rejects, denoted by B(x) = 0.

Next, we recall the definition of a pseudorandom generator (PRG).

I Definition 2. Let F be a class of functions f : {0, 1} n ae {0, 1}. An Á-PRG for F is a function G : {0, 1} s ae {0, 1} n such that for every f oe F,

We say that G Á-fools F if it is an Á-PRG for F. The input length s is the seed length of the PRG G. We say a generator is explicit, if given as input a seed x oe {0, 1} s , the output is computable in space O(s).

In a seminal work, Nisan constructed an explicit PRG that Á-fools length-n width-w ordered roBPs with seed length O (log n • log(nw/Á)). Since then, many PRGs with improved seed lengths were constructed for sub-classes of ordered roBPs (see [5,10,20] and the references therein), but Nisan's PRG remains the state-of-the-art even for width-4 general roBPs.

Nisan's PRG (and [15,9]) crucially relies on the following "communication" argument: The first half of the roBP can only communicate log w bits (describing the state reached at the end of the first half) to the second half. Due to this, it is possible to reuse all but log w bits from the seed that is used to generate the first half of the pseudorandom input, when generating the second half of the pseudorandom input. Recursively applying the idea gives the log n log(nw/Á) seed length of Nisan's PRG.

However, some researchers have the feeling that this type of argument is inherently limited to having seed length at least log 2 n [6, 26, 28] 1 , and di erent approaches are required to I Definition 3. Let B be an ordered roBP with length n and width w. We say that B is a regular roBP, if for every t oe [n] and every v oe [w], there are exactly

In [12], an  O(log n • log 1/Á)-seed length PRG with error Á is constructed for ordered unbounded-width permutation roBP with length-n and a single accept state. A later work [25] (building on a prior work [1]) constructed an  O(log n •  log(n/Á) + log(1/Á))-seed length weighted PRG for the same class. 2

Our Results

In this work, we consider two even stronger models of roBPs: (1) roBPs that are both unordered and have unbounded width and (2) roBPs that can read input in an adaptive order (that is, the next bit to read can depend on the current state).

Unordered and Unbounded-width roBPs

Given the recent developments on unordered roBPs and on unbounded-width roBPs, a natural question is whether one can construct non-trivial PRGs for unordered and unbounded-width (permutation or regular) roBPs. A prior, it is even unclear whether such a class admits non-explicit PRGs with short seed length, since the usual probabilistic argument for the existence of PRGs with short seed length does not apply here [12].

Our first result is a polylog(n/Á)-seed-length PRG for unordered unbounded-width permutation roBPs with a single accept state, significantly improving the previous (n)-seed length PRGs from [18]. 2 A weighted PRG for a class of functions F is a pair of functions G : {0, 1} s ae {0, 1} n and fl : {0, 1} s ae R

I C A L P 2 0 2 3

39:4

New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs I Theorem 4 (Unbounded width permutation BP). For all integers n and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n with seed length

that fools unordered unbounded-width permutation branching programs with a single accept state.

Our second result is a  O ( Ô n log(1/Á))-seed-length PRG for unordered unbounded-width regular roBPs with a single accept state. No (even non-explicit) non-trivial PRG is known for this class even in the ordered setting; Bogdanov, Hoza, Prakriya, and Pyne [3] has constructed  O (log n • log(1/Á))-seed-length HSG for the ordered case. 3I Theorem 5 (Unbounded width regular BP). For all integers n and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n with seed length

that fools unordered unbounded-width regular branching programs with a single accept state.

In terms of techniques, we indeed prove that the Forbes-Kelly PRG su ces for the two theorems above. Our analysis carefully modifies the original analysis from [8]. In fact, we prove that a single round of Forbes-Kelly pseudorandom restriction fools unordered unbounded-width regular roBPs (see Theorem 10). Iterating this restriction O(log(n/Á)) times proves Theorem 4. Unfortunately, it is unclear whether the same iterative construction fools unordered unbounded-width regular roBPs since they are not closed under restrictions. Still, doing the pseudorandom restriction exactly once with the right parameters proves Theorem 5.

Adaptive roBPs

While an unordered roBP can read its input in any order, it cannot change the ordering based on the input it has read so far (i.e., the order is input oblivious). We also consider an even stronger variant of roBPs, called adaptive roBPs, which are programs that can decide the next bit to read given its current state. We formally define them as follows.

I Definition 6. An adaptive read-once branching program B of length n and width w computes a function

where V i consists of the w states in the i-th layer. On an input x oe {0, 1} n , the branching program B computes as follows. It starts at a fixed start state v 0 oe [w]. Then for every t = 1, 2, . . . , n, it reads the bit x pos(t≠1,vt≠1) and updates its state according to a transition function

is a function specifying the index of the next bit to read given the current state v t≠1 . We require that on every input x oe {0, 1} n , B reads each bit in x exactly once.

We remark that adaptive roBPs are strictly stronger than unordered roBPs as shown by an example function

Here, y R denotes the reversed string of y. Observe that there is a constant-width adaptive roBP for f . The program first reads b. If b = 0, the program reads and compares x and y bit by bit. Otherwise, the program compares x and y R bit by bit. Moreover, it is easy to see (via a communication complexity argument) that every unordered roBP for f requires exponential width.

Our third result gives O(polylog(nw/Á))-seed-length PRG for adaptive roBPs. To the best of our knowledge, no explicit PRGs with seed length less than n was known prior to our work. I Theorem 7. For every n, w Ø 1 and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n fooling width-w adaptive roBPs with seed length s = O(log n • log 2 (nw/Á)).

We prove Theorem 7 by adapting the argument in [8]. The key observation allowing us to do so is the following. Suppose B satisfies the read-once promise. Then, for every vertex v oe V i , if we denote by Pre v (resp. Post v ) the set of possible variables read in any path from the starting state to v (resp. v to the accepting state). It must be the case that Pre v and Post v are disjoint for every v. By a delicate argument (Claim 15), we show that this disjointness property is su cient for applying the key technique of Forbes-Kelley proof: decomposing the branching program by high/low-degree Fourier terms.

Moreover, when the width w of the adaptive roBP is small, we can show that the branching program has bounded Fourier growth (following [7]). In particular, we show that the L-th level Fourier mass of a width-w adaptive roBP is bounded by O(log(nw)) 2Lw . As shown in [8], for programs with bounded Fourier growth, we can further improve the seed length by a log(n) factor. Formally, we show I Theorem 8. For every n, w Ø 1 and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n fooling width-w adaptive roBPs with seed length s = Â O(w log 2 (n/Á)).

Theorem 8 is a direct corollary of the new Fourier growth bound. We briefly comment on how we get the Fourier growth of O(log n) 2Lw for adaptive roBP. Roughly speaking, given a width-w, length-n adaptive roBP B, we construct a related witdh-2w, length-n 2 oblivious roBP B Õ , such that the Fourier spectrum of B is "dominated" by that of B Õ . The idea is simple: we duplicate each input of B for n times and get n 2 bits. Now, it is easy to construct a width-2w oblivious roBP running on the n 2 bits to simulate B. (Essentially, the n 2 bits allow us to make n passes over the input, we can use each pass to implement one step of transition of B.)

Although B Õ has n 2 input bits, we can exploit the promise that B is read-once, and prove the following nice property: For any input z oe {0, 1} n 2 , B Õ (z) depends only on n bits of z (that is to say, there is a subset of n bits from z, such that flipping all other bits of z cannot change the output). This allows us to connect the Fourier weights of B Õ and B. The details can be found in Appendix A.

Preliminaries

For a Boolean predicate P , we use 1 {P } to denote the indicator of P , which takes value 1 if P holds, value 0 otherwise. We often use U n to denote the uniform distribution over {0, 1} n (when n is clear from the context, we will just write U for simplicity), and U (X) to denote the uniform distribution over a set X. For two strings -,oe {0, 1} n , we use -• -and -+to denote their bit-wise AND and bit-wise XOR, respectively. Similarly, for two distributions We always work with the {≠1, 1} n basis for Boolean function analysis. For a function f : {≠1, 1} n ae R, recall that its Fourier characters indexed by -™ [n], is defined by

We often use greek letters (such as -, -, ") to index Fourier characters. We will need k-wise independent and "-almost k-wise independent distributions throughout the paper, which look locally uniform and thus fool functions that only depend on a few bits.

I Definition 9. Let D be a distribution over {0, 1} n . We say D is k-wise independent if, for every f : {0, 1} n ae [≠1, 1] that depends on at most k bits, we have

for every such f , we say that D is "-almost k-wise independent.

It is possible to sample from a k-wise independent distribution using O(k • log n) random bits ( [30]) and from a "-almost k-wise independent distribution using O(k + log log n + log 1/") random bits ( [21,2]).

PRGs for Unbounded-width Branching Programs

In this section, we will prove the following theorem, which shows that one round of pseudorandom restriction fools regular branching programs with unbounded width and a single accept state.

I Theorem 10. Let B be an unbounded-width regular branching program of length n with starting state s oe V 0 and a single accept state t oe V n . Let D, U denote a 2k-wise independent distribution and a uniform distribution over {0, 1} n , respectively. Let T (a) denote a 2k-wise independent distribution over [a] n , and let distribution T be defined as

Since the class of permutation BPs is closed under restrictions, we can iteratively apply Theorem 10 to it with k = log(n) and a = 2. The immediate consequence is that we get a PRG for unordered unbounded-width permutation branching programs.

I Corollary 11 (Restating Theorem 4). For all integers n and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n with seed length

that fools unordered unbounded-width permutation branching programs with a single accept state.

However, when it comes to regular branching programs, this class is no longer closed under restrictions. Hence we can only apply Theorem 10 once and set k

It remains an interesting open problem to apply iterative restriction for unbounded-width regular branching programs.

I Corollary 12 (Restating Theorem 5). For all integers n and Á > 0, there is an explicit Á-PRG G : {0, 1} s ae {0, 1} n with seed length

that fools unordered unbounded-width regular branching programs with a single accept state.

We will prove Theorem 10 in Subsection 3.1 and Subsection 3.2. In Subsection 3.3, we prove Corollary 11 and Corollary 12.

Fourier Decomposition of Regular BPs

Recall that V i is the set of nodes in the i-th level of our branching program. s oe V 0 is the starting point and t oe V n is the unique accepting state. x oe {0, 1} n is the input to our branching program B. In order to work with {≠1, 1} basis, we let y i = (≠1) xi for all i oe [n].

For any two nodes a oe V i and b oe V j . We define the indicator P a,b : {≠1, +1} n ae {0, 1}, Its Fourier expansion is as follows:

where the Fourier characters are defined as

This naturally extends P a,b to R n ae R. Furthermore, we define

which is the sum all the degree k terms that contain y j . We also define

which is the sum all the degree k terms that contain y i+1 .

I Fact 13. Let D, T, U be the distributions defined in Theorem 10, and let G be a distribution defined as

. Proof. Notice that when y i = (≠1) xi for all i, B(x) = P s,t (y). The first fact holds because for all -" = ?, we have

Then, we have E[B(U

For the second fact, conditioned on an instantiation of T , we define an intermediate distribution G Õ as

When

uniformly and independently from {±1}.

When T i = 0, we always have

Hence for all -, we know that

As a result, E y≥G Õ [P s,t (y)] = E y≥G [P s,t (y)]. This finishes the proof. J

Bounding the Error

In the error analysis, we follow the approach of Forbes and Kelley [8]. By Fact 13, the result we wish to prove is equivalent to ---Ey≥G[Ps,t(y)] ≠ ‚ P s,t (?)

In the analysis of [8], they considered the decomposition,

Here L k (y) are the low-degree terms, and

s,m (y) • P m,t (y) are the terms that reaches degree k exactly at node m oe V i . The intuition is that the 2k-wise independent distribution D fools L k (y) while the high-degree terms are fooled by T • U .

However, in order to work for unbounded-width regular branching programs, we have to consider a di erent decomposition. Let L k (y) be the same as before. We have

Observe that we are using

. The benefit of this decomposition is that now for all y, we have

since from s only one state m can be reached under input y. In contrast, in the original decomposition, q moeVi P m,t (y) 2 could be very large. This di erence will be essential in our analysis. Now we are ready to prove Theorem 10.

Proof of Theorem 10. By our decomposition, we know

Since G is k-wise independent, we know E y≥G [L k (y)] = 0. Now we bound the second term. We will need the following fact: For any two (not necessarily independent) sequences of random variables {f m } moeVi , {g m } moeVi , we have

. This is the Cauchy-Schwarz Inequality for random variables.

Let

We bound these two separately. We first bound E y≥G Ë q

By 2k-wise independence of G, we know for all -" = -and |-| + |-| AE 2k, the cross term

For the square terms, notice that for all T i = 1, we have y i = 0. When T i = 0, y i = (≠1) Di . T i = 1 happens with probability 1/a. D, T are 2k-wise independent. Hence when

Hence,

The last step follows from Parseval identity. Summing over all m oe V i for a fixed i, we get

The last step is because now y ≥ U , and the branching program is regular so that q moeVi E y≥U [P m,t (y)] = 1.foot_2 On the other hand, as we mentioned, for any y, s can reach a single vertex in V i , hence

Putting these two together, we get

n. J

Applications

Finally, we prove Corollary 11 and Corollary 12 in the rest of this section.

Proof of Corollary 11. Let {D (i) } ioe [¸] , {T (i) } ioe [¸] be ¸independent copies of 2k-wise independent dsitributions defined in Theorem 10 with k = log ! n Á " + log log( n Á ) + 1 and a = 2. We construct pseudorandom distributions G (0) , G (1) , . . . , G (¸) with ¸= (log(n/Á)). We let G 0 be the set of all one strings in {0, 1} n and set

Let branching program B (i) be defined as B (¸) = B and

Since any restriction of a permutation branching program is still a permutation branching program. For any realization of D (i) and T (i) , Theorem 10 says that,

.

From a standard Cherno bound, with probability at least 1 ≠ Á/2, T (1) • T (2)

does not depend on its input when T (1) • T (2) • • • • • T (¸) = 0000 . . . 0.

On the other hand, by definition, we know

. Hence a hybrid argument proves that

Proof of Corollary 12. For regular branching programs, let D and T be 2k-wise independent distributions defined in Theorem 10 with k = 2

.

We let D Õ be another independent copy of D.

We construct pseudorandom distribution G = D + T • D Õ . From Theorem 10, we know that

From Markov inequality, we get that Pr

We believe the seed length in Corollary 11 can be improved to O(log 2 n•log(n/Á)) following the sharper analysis in Section 7.1 of [8]. However, for the simplicity of presentation, we choose to only present it for the seed length of O(log n • log 2 (n/Á)).

PRGs for Adaptive Branching Programs

In this section, we prove our results for adaptive roBPs.

Decomposition of roBPs

As before, We use B : {0, 1} n ae {0, 1} to denote the adaptive branching program we are analyzing and use P : {±1} n ae {0, 1} to denote the function computed by BP over {±1} basis. For every input x oe {0, 1} n , define y oe {±1} n as y i = (≠1) xi for every i oe [n], and I C A L P 2 0 2 3 define P (y) = B(x). For any state v in the program, we denote by pos v the index of the variable queried on state v. We have two outgoing edges from v, one marked with x pos v = 0 and another with x pos v = 1.

For any state v in the program, we denote by Pre v the set of variables read in any path from the starting state to v, and by Post v the set of variables read in any path from v to the accepting state. We observe that Pre v and Post v are disjoint as otherwise there exists a path from the starting state to the accepting state (and passes through v) and reads the same variable twice.

Formally, suppose there exists a vertex v and an index i oe Pre v fl Post v . We choose a computation path fi from starting vertex v 0 to v that queries the set S ™ [n] of variables, and a path fi Õ from v to the final layer that queries the set T ™ [n], where i oe S.

We can construct an input x oe {0, 1} n that guides the program to follow the computational path of fi ¶ fi Õ . Each time the program reads a variable x j , if x j has been queried before, this clearly violates the read-once requirement. Otherwise, we can set x j to make the program follow the path of fi ¶ fi Õ . However, since know x i is queried at least twice along the path, there must be some point, where the "read-once" requirement is violated.

Define P : {≠1, 1} n ae {0, 1} as the function computed by the program. For a state v in the branching program, we denote by P aev the event that the path from the starting state passes through v. Note that P aev can be described as a branching program on the variables Pre v . We denote by P vae the sub-program of P starting at v. Note that P vae can be described as a branching program on the variables Post v .

Fourier Decomposition for Adaptive BP

Recall that the Fourier representation of any function f : {±1} n ae R is q where the second equality holds due to the following reason. For any -™ -let X -be the set of strings on which the program reads -and doesn't read -\ -. We note that if x oe X -for some set -which is a strict subset of -, then also x Õ := x ü e i for i oe -\ -is in X -, since the path for both x and x Õ will be the same (as the path doesn't query x i ). We see that the inputs in X -can be partitioned to pairs, and each pair contributed 0 to E y≥{±1} n [‰ -(y)].

For any x for which B(x) reads all the variables in -, there is a unique state v along the path such that B reads exactly k variables in -before v, and B reads the k + 1 variable from -immediately on the edge that goes out from v.

Thus, we can partition these paths according to the state v. We observe that v is the state immediately before reading the k + 1 variable in -if |Pre v fl -| = k and if pos v oe -. This gives