Steinke, Thomas AlexanderVadhan, SalilWan, Andrew2015-07-272014Steinke, Thomas, Salil Vadhan, and Andrew Wan. "Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs." In Leibniz International Proceedings in Informatics (LIPIcs), the 18th International Workshop on Randomization and Computation (RANDOM `14), Barcelona, Spain, September 4-6, 2014: 885-899.1868-8969http://nrs.harvard.edu/urn-3:HUL.InstRepos:17706522We present an explicit pseudorandom generator for oblivious, read-once, width-3 branching programs, which can read their input bits in any order. The generator has seed length O~( log^3 n ). The previously best known seed length for this model is n^{1/2+o(1)} due to Impagliazzo, Meka, and Zuckerman (FOCS'12). Our work generalizes a recent result of Reingold, Steinke, and Vadhan (RANDOM'13) for permutation branching programs. The main technical novelty underlying our generator is a new bound on the Fourier growth of width-3, oblivious, read-once branching programs. Specifically, we show that for any f : {0,1}^n -> {0,1} computed by such a branching program, and k in [n], sum_{|s|=k} |hat{f}(s)| < n^2 * (O(\log n))^k, where f(x) = sum_s hat{f}(s) (-1)^<s,x> is the standard Fourier transform over Z_2^n. The base O(log n) of the Fourier growth is tight up to a factor of log log n.en-USPseudorandomnessBranching ProgramsDiscrete Fourier AnalysisConference Paper2015-07-2710.4230/LIPIcs.APPROX-RANDOM.2014.885