2026-07-22T17:01:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17124 2024-03-06T10:59:01Z ddc:004 open_access

Fourier Growth of Regular Branching Programs Lee, Chin Ho Pyne, Edward Vadhan, Salil pseudorandomness fourier analysis We analyze the Fourier growth, i.e. the L₁ Fourier weight at level k (denoted L_{1,k}), of read-once regular branching programs. We prove that every read-once regular branching program B of width w ∈ [1,∞] with s accepting states on n-bit inputs must have its L_{1,k} bounded by min{Pr[B(U_n) = 1](w-1)^k, s ⋅ O((n log n)/k)^{(k-1)/2}}. For any constant k, our result is tight up to constant factors for the AND function on w-1 bits, and is tight up to polylogarithmic factors for unbounded width programs. In particular, for k = 1 we have L_{1,1}(B) ≤ s, with no dependence on the width w of the program. Our result gives new bounds on the coin problem and new pseudorandom generators (PRGs). Furthermore, we obtain an explicit generator for unordered permutation branching programs of unbounded width with a constant factor stretch, where no PRG was previously known. Applying a composition theorem of Błasiok, Ivanov, Jin, Lee, Servedio and Viola (RANDOM 2021), we extend our results to "generalized group products," a generalization of modular sums and product tests. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Chin Ho Lee and Edward Pyne and Salil Vadhan 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.2 urn:nbn:de:0030-drops-171247 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode