We present an explicit pseudorandom generator for oblivious, read-once, permutation branching programs of constant width that can read their input bits in any order. The seed length is *O(*log* ^{2} n)*, where

Our pseudorandom generator is similar to the one used by Gopalan et al. (FOCS 2012) for read-once CNFs, but the analysis is quite different; ours is based on Fourier analysis of branching programs. In particular, we show that an oblivious, read-once, *regular* branching program of width *w* has Fourier mass at most *(2w) ^{2k}* at level

Published: | RANDOM 2013 |

Full Version: | arXiv |

Bibtex: |
@inproceedings{ReingoldSteinkeVadhan2013, author = {Omer Reingold and Thomas Steinke and Salil Vadhan}, title = {Pseudorandomness for Regular Branching Programs via Fourier Analysis}, booktitle = {APPROX-RANDOM}, year = {2013}, pages = {655--670}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, editor = {Prasad Raghavendra and Sofya Raskhodnikova and Klaus Jansen and Jos\'e Rolim} } |

Last updated on 12 June 2013 by Thomas Steinke.