2026-07-20T05:28:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4745 2024-03-06T10:35:22Z ddc:004 open_access

Pseudorandomness and Fourier Growth Bounds for Width-3 Branching Programs Steinke, Thomas Vadhan, Salil Wan, Andrew Pseudorandomness Branching Programs Discrete Fourier Analysis We 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Steinke and Salil Vadhan and Andrew Wan 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.885 urn:nbn:de:0030-drops-47456 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.885 eng https://creativecommons.org/licenses/by/3.0/legalcode