Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-083 | 29th June 2012 23:55

Pseudorandomness for Permutation Branching Programs Without the Group Theory

RSS-Feed

Abstract:

We exhibit an explicit pseudorandom generator that stretches an $O \left( \left( w^4 \log w + \log (1/\varepsilon) \right) \cdot \log n \right)$-bit random seed to $n$ pseudorandom bits that cannot be distinguished from truly random bits by a permutation branching program of width $w$ with probability more than $\varepsilon$. This improves on the seed length $O \left( \left( (w!)^{11} + \log (1/\varepsilon) \right) \cdot \log n \right)$ of Koucky, Nimbhorkar, and Pudlak and $O \left( \left( w^8 + \log (1/\varepsilon) \right) \cdot \log n \right)$ of De. More importantly, the analysis of our generator uses only combinatorial and linear-algebraic arguments, whereas the previous proofs refer to groups or representation theory.



ISSN 1433-8092 | Imprint