Pseudorandom Bits for Non-Commutative Programs

A main agenda is obtaining explicit pseudorandom generators for read-once branching programs (ROBPs), with an ultimate goal of proving $\text{BPL}=\text{L}$. However, even for constant-width, permutation ROBPs, the best known seed length is $\ge \log n\log (1/\epsilon )$. This is $\ge {\log }^{2}n$ when $\epsilon =1/n$, and thus falls short of the optimal seed length $c\log (n/\epsilon )$. For permutation ROBPs of width $w$, seed length $c_w\log (n/\epsilon )\log ({\epsilon }^{-1}\log n)$ follows from instantiating the “Polarizing Random Walks” [9] with a bound from [43, 28]. These generators work in any order; thus they essentially match the seed length $c_w\log (n/\epsilon )\log (1/\epsilon )$ that was already available for fixed-order in a sequence of exciting works culminating in [46].

The class of permutation ROBPs is equivalent to group programs (see e.g. [25]):

No generator with seed length less than $\log n\log (1/\epsilon )$ was available for any non-commutative group. While optimal seed length $c\log (n/\epsilon )$ was known for ${\mathbb{Z}}_2$ since [40], it took nearly 20 years and different techniques to have the same seed length over ${\mathbb{Z}}_3$ [35, 38], and remarkably that seed length is still not available even for ${\mathbb{Z}}_6$ (see [18] for the best known construction).

Another model that has received significant attention is read-once polynomials. Intuitively, this model can serve as a bridge between permutation and non-permutation ROBPs. The available generators for non-permutation ROBPs have significantly worse seed length than for permutation programs, see e.g. [37] and the discussion there.

A sequence of works [30, 37, 14] culminated in PRGs with seed length $c\log n+\log (1/\epsilon ){\log }^c\log (1/\epsilon )$ for read-once polynomials over ${\mathbb{Z}}_2$. But for other domains such as ${\mathbb{Z}}_3$ such good seed lengths were not known.

A more general model that generalizes and unifies the previous ones is what we call block-products of width $w$ over a group $G$. Here, the input bits are arbitrarily partitioned in blocks of $w$ bits, arbitrary Boolean functions are then applied to each block, and finally the outputs are used as exponents to group elements. For our results, we will need to allow one block to be larger; we call this spill and incorporate it in the following definition.

Note that block products are unordered by definition. They are a generalization of several function classes that have been studied, including modular sums [34, 39, 18] (when $G$ is a cyclic group and $w=1$), product tests with outputs in $\{-1,1\}$ (a.k.a. combinatorial checkerboards) [52, 23, 29, 31, 27] (when $G={\mathbb{Z}}_2$), themselves a generalization of combinatorial rectangles [5, 36, 19], and unordered combinatorial shapes [20, 18] (when $G={\mathbb{Z}}_{m+1}$). Block products also generalize read-once polynomials because one can show (for the uniform and typically also pseudorandom distributions) that monomials of degree $\ge \log (n/\epsilon )$ do not affect the result significantly, and so one can simulate these polynomials with blocks of size $\log (n/\epsilon )$.

In terms of generators, a series of works culminating in [27] gives nearly-optimal seed length (i.e., $w+\log (\mathrm{\ell }/\epsilon )$ up to lower-order factors) over ${\mathbb{Z}}_2$. But such a result was not known over other groups such as ${\mathbb{Z}}_3$ or any non-commutative group.

We proceed by induction on $k$. If $k=1$, then $G$ is cyclic. We can take a generator $a\in G$ and define the 1-1 mapping $G\ni a^z\leftrightarrow z\in {𝔽}_p$. So ${\prod }_{i=1}^n{g}_i^{x_i}={\prod }_{i=1}^n{a}^{z_i{x}_i}$ can be written as the degree-1 polynomial ${\sum }_{i=1}^n{z}_i{x}_i$.

Otherwise, $G$ has a normal subgroup $H$ of order $p^{k-1}$ [15, Chapter 6, Theorem 1.(3)]. The corresponding quotient group $Q=G/H$ has order $p$ and is therefore cyclic. So we can write $g_i\in G$ as

where $h_i\in H$ and $a$ is a generator of $Q$. Applying the induction hypothesis on $H$, we can identify each element $g_i=a^{e_i}{h}_i$ with a $k$-tuple $(e_i,e_i^{\prime })\in {𝔽}_p^k$, where $e_i^{\prime }\in {𝔽}_p^{k-1}$ corresponds to $h_i\in H$.

Now we apply the conjugation trick as in [6], and use induction. That is, let $b_i:=a^{{\sum }_{j\le i}{e}_j{x}_j}$ and write

Note that $b_i$ and $b_i^{-1}$ can be computed by some degree-1 polynomials over ${𝔽}_p$, and $h_i^{x_i}$ can be (trivially) computed by a degree-$c_H$ polynomial over ${𝔽}_p$.

Therefore, each term $b_i{h}_i^{x_i}{b}_i^{-1}$ can be computed by some degree-$c_G$ polynomial map $f^{H,i}=(f_1,\mathrm{\dots },f_k)$ over ${𝔽}_p$. Moreover, these terms lie in $H$ because $H$ is a normal subgroup of $G$. Hence we have reduced to a product over $H$, which by induction hypothesis, can be computed by some degree-$c_H$ polynomial, and the result follows. $◀$

Given Lemma 13, it suffices to construct a bit-generator that fools low-degree polynomials over ${𝔽}_p$.

For this case, we can simply combine Lemma 13 with known generators for polynomials over ${𝔽}_2$ [8, 32, 51]. In fact, we obtain results for non-read-once programs as well, and of any length. (Indeed, such polynomials are equivalent to low-degree polynomials over ${𝔽}_2$.)

Here we need additional ideas because bit-generators that fool polynomials over ${𝔽}_q$ with $q\ne 2$ are not known. However, the works [8, 32, 51] do give generators that output field elements that fool such polynomials.

However, we need distributions over ${\{0,1\}}^n$. This distinction is critical and arises in a number of previous works. Currently, for domain ${\{0,1\}}^n$ only weaker results with seed length $\ge {\log }^{2}n$ are known [33].

Still, as pointed out in [35, 38], Lemma 15 implies results over the domain ${𝔽}_2^n$ for biased bits:

Let $Y=(Y_1,Y_2,\mathrm{\dots },Y_n)$ be the distribution from Lemma 15, for degree $d(p-1)$. Define $X:=(Y_1^{p-1},Y_2^{p-1},\mathrm{\dots },Y_n^{p-1})$. Note $X$ is over ${\{0,1\}}^n$. Also, if $U$ is uniform in ${𝔽}_p$ then $U^{p-1}=N_p$. The result follows. $◀$ We will show how to use biased bits. For this we use that the program is read-once.

This follows from Lemma 7.2 in [16] combined with the Fourier bound in [43, 28]. The proof in [16] is for the fixed noise parameter $p=4$, but the generalization to any $p$ is immediate (replace $1/2$ with $1-2/p$ in the last two lines of the proof). $◀$ We now have all the ingredients.

Use Lemma 18. Averaging over $X$, it suffices to derandomize $N_p$. By Lemma 13 it suffices to do this for low-degree polynomials. This follows from Corollary 17. $◀$

Let $M$ be a square complex matrix. We denote by $\mathrm{tr}(M)$ the trace of $M$, by $\overline{M}$ the conjugate of $M$, by $M^T$ the transpose of $M$, and by $M^{\ast }$ the conjugate transpose $\overline{M^T}$ (aka adjoint, Hermitian conjugate, etc.). The matrix $M$ is unitary if the rows and the columns are orthonormal; equivalently $M^{-1}=M^{\ast }$.

The Frobenius norm, (a.k.a. Schatten 2-norm, Hilbert–Schmidt operator) of a square matrix $M$, denoted ${\parallel M\parallel }_{𝖥}$, is ${\sum }_{i,j}{|M_{i,j}|}^2=\mathrm{tr}(M{M}^{\ast })$.

The operator norm of a matrix $M$, denoted ${\parallel M\parallel }_{\mathrm{𝗈𝗉}}$, is the square root of the largest eigenvalue of the matrix $M{M}^{\ast }$. In particular, if $M$ is a normal matrix, i.e. $M{M}^{\ast }=M^{\ast }M$, then ${\parallel M\parallel }_{\mathrm{𝗈𝗉}}$ equals its largest eigenvalue in magnitude.

Let $G$ be a group. A representation $\rho$ of $G$ with dimension $d$ maps elements of $G$ to $d\times d$ unitary, complex matrices so that $\rho (xy)=\rho (x)\rho (y)$. Thus, $\rho$ is a homomorphism from $G$ to the group of linear transformations of the vector space ${ℂ}^d$. We denote by $d_{\rho }$ the dimension of $\rho$.

If there is a non-trivial subspace $W$ of ${ℂ}^d$ that is invariant under $\rho$, that is, $\rho (x)W\subseteq W$ for every $x\in G$, then $\rho$ is reducible; otherwise it is irreducible. Irreducible representations are abbreviated irreps and play a critical role in Fourier analysis. We denote by $\widehat{G}$ a complete set of inequivalent irreducible representations of $G$.

Let $\widehat{G}$ be the set of irreducible representations of $G$ (i.e. the dual group of $G$). We have

For a random variable $Z$ we also use $Z$ to denote its probability mass function.

For an irrep $\rho \in \widehat{G}$, the $\rho$-th Fourier coefficient of $Z$ is

The Fourier expansion of $Z:G\to ℝ$ is

Parseval’s identity gives

$\mathrm{⊲}$

As $M$ is unitary, we can write $M=Q^{\ast }DQ$, where $D$ is a diagonal matrix with $M$’s eigenvalues on its diagonal and $Q$ is unitary. The eigenvalues of $(I+M)/2=Q^{\ast }(\frac{I+D}{2})Q$ are $\frac{1+e^{i{\theta }_j}}{2}=e^{i{\theta }_j/2}\cdot \frac{e^{-i{\theta }_j/2}+e^{i{\theta }_j/2}}{2}=e^{i{\theta }_j/2}\cos ({\theta }_j/2)$, which have magnitudes at most $|\cos ({\theta }_j/2)|\le 1-{\theta }^2/8$. $\mathrm{⊲}$

Let $T$ be the $t$ coordinates $j$ where $\rho (g_j)\ne I_{d_{\rho }}$. For every fixing of the other coordinates, we can write $f_{\rho }(U)$ as

for some unitary matrices $B$ and $B_j$’s. So

$\mathrm{⊲}$

We now proceed with the proof of the main result. The proof extends to handle the spill, but for simplicity we do not discuss it here. We fool each irreducible representation of $G$ separately and then appeal to Claim 21. Fix a representation $\rho$ and consider the product

Let $t$ be the number of non-identity elements $\rho (g_j):j\in [n]$ and $S$ be their coordinates.

Let us sketch the construction. First, XORing with an almost $2c_G\log (1/\epsilon )$-wise uniform distribution takes care of the case $t\le c_G\log (1/\epsilon )$, so we may assume that $t$ is larger. In this case, by Claim 23, we have that the bias ${\parallel 𝐄[f_{\rho }(U)]\parallel }_{\mathrm{𝗈𝗉}}$ is small under the uniform distribution. Our goal is to set $ct$ bits in $S$ to uniform and apply Claim 23 again.

Let $\mathrm{\ell }:=c_G\log (1/\epsilon )$. Let $M$ be a $(\log n)\times 10\mathrm{\ell }$ matrix filled with uniform bits.

We will make $\log n$ guesses of $t$. For each guess $v=2^i\cdot \mathrm{\ell }:i\in \{0,\mathrm{\dots },\log n-1\}$ of $t$, we select a subset of size $\mathrm{\ell }$ of the input positions using a hash function $h_i$, and then hash these $\mathrm{\ell }$ positions to row $i$ of $M$ using another hash function $h$, and assign input bits correspondingly. The final generator is obtained by trying all guesses, using the same seed for each guess $h_i$, and XORing together the bits.

In more detail, for each $i\in \{0,\mathrm{\dots },\log n-1\}$, let $h_i:[n]\to \{0,1\}$ be a $10\mathrm{\ell }$-wise independent hash family with ${𝐏𝐫}_{h_i}[h_i(j)=1]=2^{-i}$ for each $j\in [n]$. Let $h:[n]\to [10\mathrm{\ell }]$ be another $5\mathrm{\ell }$-wise uniform hash family. The output of our generator is

where the $j$-th bit of $D^{(i)}$ is

We use the same seed to sample $h_0,\mathrm{\dots },h_{\log n-1}$, which costs at most $O_G(\log n\log (1/\epsilon ))$ bits [49, Corollary 3.34]. Sampling $h$ uses another $O_G(\log (n/\epsilon )\log (1/\epsilon ))$ bits. This uses a total of $O_G(\log (n/\epsilon )\log (1/\epsilon ))$ bits.

We now show that ${\parallel 𝐄[f_{\rho }(D)]\parallel }_{\mathrm{𝗈𝗉}}\le O(\epsilon )$. Suppose $t\in [2^i\mathrm{\ell },2^{i+1}\mathrm{\ell }]$. Recall that $S$ are the coordinates corresponding to the non-identity matrices in the product. Let $J:=h_i^{-1}\{1\}\cap S$. As $𝐏𝐫[h_i(j)=1]=2^{-i}$, we have $𝐄[|J|]\in [\mathrm{\ell },2\mathrm{\ell }]$. Applying tail bounds for bounded independence (see Lemma 36), we have $|J|\in [\mathrm{\ell }/2,3\mathrm{\ell }]$ except with probability $\epsilon$. Conditioned on this event, as $|J|\le 3\mathrm{\ell }$ and $h$ is $5\mathrm{\ell }$-wise uniform, we can think of $h$ as a random function from $J$ to $[10\mathrm{\ell }]$. Hence, for each $j\in [10\mathrm{\ell }]$, we have

By a Chernoff bound, we have that except with probability at most $\epsilon$, the number of $j$ such that $|J\cap h^{-1}(j)|=1$ is at least $\mathrm{\ell }/10$.

Let $T$ be these coordinates. Fixing all the bits in $M$ except the ones in row $i$ that are fed into $T$, we can write the conditional expectation of $f_{\rho }(G)$ over the bits in $T$ as

for some unitary matrices $B$, $A_j$’s and $B_j$’s, and in particular, $A_j$ has its eigenvalues bounded away from 1 on the complex unit circle. Therefore, by Claim 22,

We iterate Theorem 26 repeatedly for some $t$ times to reduce the problem to fooling an $O(\log (m/\epsilon ))$-junta which can be done using an almost bounded uniform distribution.

Given an $(\mathrm{\ell },w,\log (1/\epsilon ))$-product $f$, let $w^{\prime }=\max \{w,\log \mathrm{\ell },\log m\}$ so that we can view $f$ as an $(m^5{2}^{45w^{\prime }},3w^{\prime },2\log (1/\epsilon ))$-product. We first apply Theorem 26 for $t_1=O(\log w^{\prime })$ times until we have a

for some constant $C$.

Let $b:=\frac{\log (1/\epsilon )+\log m}{\log \log (1/\epsilon )+\log m}$. We will apply the following repeatedly for some $r=O_m(1)$ steps. We divide the $f_i:i\ge 1$ into groups of $b$ functions and view the product of functions in each group as a single function, this way we can think of the above product as a

So we can continue applying Theorem 26 for $t_2=O(\log (\log (1/\epsilon )+\log m))\le O_m(\log \log (1/\epsilon ))$ times and the restricted function becomes a

Repeating this process for

times, we are left with a

which can be fooled by an $\epsilon$-almost $O(\log (m/\epsilon ))$-wise uniform distribution that can be sampled using $s^{\prime }=O(\log (m/\epsilon )+\log \log n)$ bits [41, 2]. Therefore, in total we apply Theorem 26 for

times, each with a seed of

bits. Hence in total it uses

bits. $◀$