ECCC-Report TR10-113https://eccc.weizmann.ac.il/report/2010/113Comments and Revisions published for TR10-113en-usSat, 17 Jul 2010 16:52:33 +0300
Paper TR10-113
| Pseudorandom Generators for Group Products |
Michal Koucky,
Prajakta Nimbhorkar,
Pavel Pudlak
https://eccc.weizmann.ac.il/report/2010/113We 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.
Sat, 17 Jul 2010 16:52:33 +0300https://eccc.weizmann.ac.il/report/2010/113