Pseudorandomness for regular branching programs via Fourier analysis

DOI10.1007/978-3-642-40328-6_45MaRDI QIDQ2851892zbMATH OpenOpenAlexFDO

Authors Omer Reingold, Thomas Steinke, Salil Vadhan

Publication date 4 October 2013

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.3004

Mathematics Subject Classification ID

Data structures (68P05)

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(lo{g}^{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.

Recommendations

• Pseudorandomness and Fourier growth bounds for width-3 branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandom generators for regular branching programs
• Pseudorandom Bits for Oblivious Branching Programs

Cited in

(28)

• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Pseudorandomness and Fourier growth bounds for width-3 branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Pseudorandom generators for regular branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Bounded independence plus noise fools products
• Pseudorandom generators for low sensitivity functions
• Pseudorandom functions: three decades later
• Pseudorandom Bits for Oblivious Branching Programs
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Fourier bounds and pseudorandom generators for product tests
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• scientific article; zbMATH DE number 7250141 (Why is no real title available?)
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Pseudorandom generators for group products, extended abstract
• A polynomial-time construction of a hitting set for read-once branching programs of width 3
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Paradigms for Unconditional Pseudorandom Generators
• Approximating iterated multiplication of stochastic matrices in small space
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Pseudorandomness, symmetry, smoothing: I
• Pseudorandom generators for unbounded-width permutation branching programs
• Pseudodistributions that beat all pseudorandom generators
• Testing isomorphism of Boolean functions over finite abelian groups

This page was built for publication: Pseudorandomness for regular branching programs via Fourier analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2851892)