Pseudorandom generators for group products

0371063 - MÚ 2012 RIV US eng C - Conference Paper (international conference)
Koucký, Michal - Nimbhorkar, Prajakta - Pudlák, Pavel
Pseudorandom generators for group products.
Proceedings of the 43rd annual ACM Symposium on Theory of Computing (STOC 2011). New York: ACM, 2011 - (Fortnow, L.; Vadhan, S.), s. 263-272. ISBN 978-1-4503-0691-1.
[STOC 2011. Symposium on Theory of Computing /43./. San Jose (US), 06.06.2011-08.06.2011]
R&D Projects: GA ČR GAP202/10/0854; GA AV ČR IAA100190902
Institutional research plan: CEZ:AV0Z10190503
Keywords : pseudorandom generators * permutation branching programs * finite groups
Subject RIV: BA - General Mathematics
http://dl.acm.org/citation.cfm?doid=1993636.1993672

We prove that the pseudorandom generator introduced by Impagliazzo Nisan and Wigderson with proper choice of parameters fools group products of a given finite group. The seed length is logarithmic in the size of the inputs.
Permanent Link: http://hdl.handle.net/11104/0204694