Pseudorandomness for Permutation Branching Programs Without the Group Theory

Thomas Steinke

We exhibit an explicit pseudorandom generator that stretches an O(( w^4 log w + log(1/eps) ) * log n )-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 eps. This improves on the seed length O(( (w!)^{11} + log(1/eps) ) * log n ) of Koucký, Nimbhorkar, and Pudlák and O(( w^8 + log(1/eps) ) * log n ) 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.
Published: ECCC [pdf]
   author = {Thomas Steinke},
   title = {Pseudorandomness for Permutation Branching Programs Without the Group Theory},
   journal = {Electronic Colloquium on Computational Complexity (ECCC)},
   volume = {19},
   year = {2012},
   pages = {TR12-083},
   url = {},

Last updated on 2 July 2012 by Thomas Steinke.