Pseudorandom generators for group products: extended abstract

We prove that the pseudorandom generator introduced by Impagliazzo et al. (1994) with proper choice of parameters fools group products of a given finite group G. The seed length is O((|G| O(1) + log 1/δ)log n), where n is the length of the word and δ is the allowed error. The result implies that the pseudorandom generator with seed length O((2 O(w log w) + log 1/δ)log n) fools read-once permutation branching programs of width w. As an application of the pseudorandom generator one obtains small-bias spaces for products over all finite groups Meka and Zuckerman (2009).

Authors

• Michal Koucký 0001
• Prajakta Nimbhorkar
• Pavel Pudlák

Keywords

• bounded width branching programs
• pseudorandom generators
• randomized group product
• small bias spaces