Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-113 | 16th July 2010 16:57

#### Pseudorandom Generators for Group Products

TR10-113
Authors: Michal Koucky, Prajakta Nimbhorkar, Pavel Pudlak
Publication: 17th July 2010 16:52
We prove that the pseudorandom generator introduced in Impagliazzo et al. (1994) fools group products of a given finite group. The seed length is $O(\log n \log 1 / \epsilon)$, where $n$ is the length of the word and $\epsilon$ is the error. The result is equivalent to the statement that the pseudorandom generator fools read-once permutation branching programs of constant width.