Pseudorandom bits for non-commutative programs
Chin Ho Lee, Emanuele Viola · 2025
Read Pseudorandom bits for non-commutative programs by Chin Ho Lee, Emanuele Viola (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01832.txt.
Introduction
Chin Ho Lee and Emanuele Viola build fake random bits that fool programs whose steps do not commute. Many tests multiply group members in a fixed order, and a good faker must pass them with a short seed. Past fakers for non-commuting groups needed long seeds. Their 2025 results close much of that gap.
For one broad group family, their seed length is the best possible. The proof pairs a small-bias trick with noise, but makes the noise fixed to skip a costly loop. A lifting step then stretches the fakers to wider block tests. New fakers cover quaternion and mixed groups at near-best seed length. The authors flag composite moduli as the next wall, much like one in circuit theory.
Catalog record
| CREATOR | Chin Ho Lee, Emanuele Viola |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01832
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Pseudorandom bits for non-commutative programs Chin Ho Lee, Emanuele Viola Abstract We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1. We consider read-once group-products over a finite group G G , i.e., tests of the form ∏ i = 1 n g i x i \prod_{i=1}^{n}g_{i}^{x_{i}} where g i ∈ G g_{i}\in G , a special case of read-once permutation branching programs. We give generators with optimal seed length c G log ( n / ε ) c_{G}\log(n/\varepsilon) over any p p -group. The proof uses the small-bias plus noise paradigm, but derandomizes the noise to avoid the recursion in previous work. Our generator works when the bits are read in any order. Previously for any non-commutative group the best seed length was ≥ log n log ( 1 / ε ) \geq\log n\log(1/\varepsilon) , even for a fixed order. 2. We give a reduction that “lifts” suitable generators for group products over G G to a generator that fools width- w w block products , i.e., tests of the form ∏ g i f i \prod g_{i}^{f_{i}} where the f i f_{i} are arbitrary functions on disjoint blocks of w w bits. Block products generalize several previously studied classes. The reduction applies to groups that are mixing in a representation-theoretic sense that we identify. 3. Combining (2) with (1) and other works we obtain new generators for block products over the quaternions or over any commutative group, with nearly optimal seed length. In particular, we obtain generators for read-once polynomials modulo any fixed m m with nearly optimal seed length. Previously this was known only for m = 2 m=2 . 4. We give a new generator for products over “mixing groups.” The construction departs from previous work and uses representation theory. For constant error, we obtain optimal seed length, improving on previous work (which applied to any group). This paper identifies a challenge in the area that is reminiscent of a roadblock in circuit complexity – handling composite moduli – and points to several classes of groups to be attacked next. 1 Introduction The construction of explicit pseudorandom generators is a fundamental research goal that has applications in many areas of theoretical computer science. For background we refer to the recent survey [ HH24 ] . We first define pseudorandom generators, incorporating the variants of any order (reflected in the permutation \pi ) and non-Boolean tests (reflected in the range set R ). Definition 1 (Pseudorandom generators (PRGs)) . An explicit function P\colon\{0,1\}^{s}\to\{0,1\}^{n} is a pseudorandom generator (PRG) with seed length s and error \varepsilon for a class of functions F mapping \{0,1\}^{n} to a set R if for every f\in F the statistical distance between f(P(U_{s})) and f(U_{n}) is \leq\varepsilon , where U_{s} denotes the uniform distribution over \{0,1\}^{s} . We say P fools F in any order if \pi(P) fools F for any permutation \pi of the positions of the n input bits. A PRG is explicit if it is computable in time n^{c} . PRGs for branching programs, and group 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 \geq\log n\log(1/\varepsilon) . This is \geq\log^{2}n when \varepsilon=1/n , and thus falls short of the optimal seed length c\log(n/\varepsilon) . For permutation ROBPs of width w , seed length c_{w}\log(n/\varepsilon)\log(\varepsilon^{-1}\log n) follows from instantiating the “Polarizing Random Walks” [ CHHL19 ] with a bound from [ RSV13 , LPV22 ] . These generators work in any order ; thus they essentially match the seed length c_{w}\log(n/\varepsilon)\log(1/\varepsilon) that was already available for fixed-order in a sequence of exciting works culminating in [ Ste12 ] . The class of permutation ROBPs is equivalent to group programs (see e.g. [ KNP11 ] ): Definition 2 . A program (or product ) p of length n over a group G is a tuple (g_{1},g_{2},\ldots,g_{n})\in G^{n} . The program computes the function f_{p}\colon\{0,1\}^{n}\ni x\mapsto\prod_{i\in[n]}g_{i}^{x_{i}}\in G . No generator with seed length less than \log n\log(1/\varepsilon) was available for any non-commutative group. While optimal seed length c\log(n/\varepsilon) was known for \mathbb{Z}_{2} since [ NN90 ] , it took nearly 20 years and different techniques to have the same seed length over \mathbb{Z}_{3} [ LRTV09b , MZ09a ] , and remarkably that seed length is still not available even for \mathbb{Z}_{6} (see [ GKM18 ] for the best known construction). PRGs for read-once polynomials. 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. [ MRT19a ] and the discussion there. A sequence of works [ LV20a , MRT19a , DHH20 ] culminated in PRGs with seed length c\log n+\log(1/\varepsilon)\log^{c}\log(1/\varepsilon) for read-once polynomials over \mathbb{Z}_{2} . But for other domains such as \mathbb{Z}_{3} such good seed lengths were not known. PRGs for block-products. 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. Definition 3 (Block-product with spill) . A function f\colon\{0,1\}^{n}\to G is computable by a w -block product with \ell terms and a spill of q bits, written as (\ell,w,q) -product, over a group G if there exist \ell+1 disjoint subsets I_{0},I_{1},\ldots,I_{\ell}\subseteq[n] , where \lvert I_{0}\rvert\leq q and \lvert I_{i}\rvert\leq w for each i\in[\ell] such that f(x)=\prod_{i=1}^{\ell}g_{i}^{f_{i}(x_{I_{i}})} for some group elements g_{i}\in G , functions f_{i}\colon\{0,1\}^{I_{i}}\to\{0,1\} . Here x_{I_{i}} are the |I_{i}| bits of x indexed by I_{i} . Note that block products are unordered by definition. They are a generalization of several function classes that have been studied, including modular sums [ LRTV09a , MZ09b , GKM18 ] (when G is a cyclic group and w=1 ), product tests with outputs in \{-1,1\} (a.k.a. combinatorial checkerboards) [ Wat13 , HLV18 , LV18 , LV20b , Lee19 ] (when G=\mathbb{Z}_{2} ), themselves a generalization of combinatorial rectangles [ ASWZ96 , Lu02 , GMR+12 ] , and unordered combinatorial shapes [ GMRZ13 , GKM18 ] (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 \geq\log(n/\varepsilon) do not affect the result significantly, and so one can simulate these polynomials with blocks of size \log(n/\varepsilon) . In terms of generators, a series of works culminating in [ Lee19 ] gives nearly-optimal seed length (i.e., w+\log(\ell/\varepsilon) 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. 1.1 Our results In this work we bring new techniques, notably from group theory, to bear on these