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]
Bibtex:  
@article{Steinke2012,
   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 = {http://eccc.hpi-web.de/report/2012/083/},
}
 

Last updated on 2 July 2012 by Thomas Steinke.