@conference {634148,
	title = {Pseudorandomness for regular branching programs via Fourier analysis},
	booktitle = {Sofya Raskhodnikova and Jos{\'e} Rolim, editors, Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM {\textquoteleft}13), Lecture Notes in Computer Science},
	volume = {8096},
	year = {2013},
	pages = {655-670},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	abstract = {
	Version History:\&nbsp;Full version posted as ECCC TR13-086 and arXiv:1306.3004 [cs.CC].



	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\&nbsp;\(O(\log^2n)\), where\&nbsp;\(n\)\&nbsp;is the length of the branching program. The previous best seed length known for this model was\&nbsp;\(n^{1/2+o(1)}\), which follows as a special case of a generator due to Impagliazzo, Meka, and Zuckerman (FOCS 2012) (which gives a seed length of\&nbsp;\(s^{1/2+o(1)}\)\&nbsp;for arbitrary branching programs of size\&nbsp;\(s\)). Our techniques also give seed length\&nbsp;\(n^{1/2+o(1)}\)\&nbsp;for general oblivious, read-once branching programs of width \(2^{n^{o(1)}}\))\&nbsp;, which is incomparable to the results of Impagliazzo et al.



	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,\&nbsp;regular\&nbsp;branching program of width\&nbsp;\(w\)\&nbsp;has Fourier mass at most \((2w^2)^k\)\&nbsp;at level\&nbsp;\(k\), independent of the length of the program.

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-40328-6_45},
	author = {Omer Reingold and Thomas Steinke and Salil Vadhan}
}
