Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR12-083 | 29th June 2012 23:55

#### Pseudorandomness for Permutation Branching Programs Without the Group Theory

TR12-083
Authors: Thomas Steinke
Publication: 2nd July 2012 15:57
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.