Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-113 | 16th July 2010 16:57

Pseudorandom Generators for Group Products

RSS-Feed

Abstract:

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.



ISSN 1433-8092 | Imprint