Pseudorandomness for Regular Branching Programs via Fourier Analysis

DSpace/Manakin Repository

Pseudorandomness for Regular Branching Programs via Fourier Analysis

Citable link to this page


Title: Pseudorandomness for Regular Branching Programs via Fourier Analysis
Author: Reingold, Omer; Steinke, Thomas Alexander; Vadhan, Salil P.

Note: Order does not necessarily reflect citation order of authors.

Citation: Reingold, Omer, Thomas Steinke, and Salil Vadhan. 2013. “Pseudorandomness for Regular Branching Programs via Fourier Analysis.” Presented at the 17th International Workshop on Randomization and Computation (RANDOM 2013), Berkeley, CA, USA, August 21-23, 2013. In Lecture Notes in Computer Science 8096: 655–670.
Full Text & Related Files:
Abstract: 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 n is the length of the branching program. The previous best seed length known for this model was \(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 \(s^{ 1/2 + o(1)}\) for arbitrary branching programs of size s). Our techniques also give seed length \(n^{ 1/2 + o(1)}\) for general oblivious, read-once branching programs of width \(2^{n^{o(1)}}\), 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, regular branching program of width w has Fourier mass at most \((2w^ 2) ^k\) at level k, independent of the length of the program.
Published Version: doi:10.1007/978-3-642-40328-6_45
Terms of Use: This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at
Citable link to this page:
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)


Search DASH

Advanced Search