Pseudorandom generators for width-3 branching programs

DOI10.1145/3313276.3316319MaRDI QIDQ5212804zbMATH OpenOpenAlexFDO

Authors Raghu Meka, Omer Reingold, Avishay Tal

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

read-once branching programsrandom restrictionsepsilon-biased generatorpseudorandom generators for small-space computationpseudorandom generators for space-bounded computation

Mathematics Subject Classification ID

Randomized algorithms (68W20) Data structures (68P05)

Abstract: We construct pseudorandom generators of seed length $ildeO(log(n)cdotlog(1/epsilon))$ that $epsilon$-fool ordered read-once branching programs (ROBPs) of width $3$ and length $n$. For unordered ROBPs, we construct pseudorandom generators with seed length $ildeO(log(n)cdotmathrmpoly(1/epsilon))$. This is the first improvement for pseudorandom generators fooling width $3$ ROBPs since the work of Nisan [Combinatorica, 1992]. Our constructions are based on the `iterated milder restrictions' approach of Gopalan et al. [FOCS, 2012] (which further extends the Ajtai-Wigderson framework [FOCS, 1985]), combined with the INW-generator [STOC, 1994] at the last step (as analyzed by Braverman et al. [SICOMP, 2014]). For the unordered case, we combine iterated milder restrictions with the generator of Chattopadhyay et al. [CCC, 2018]. Two conceptual ideas that play an important role in our analysis are: (1) A relabeling technique allowing us to analyze a relabeled version of the given branching program, which turns out to be much easier. (2) Treating the number of colliding layers in a branching program as a progress measure and showing that it reduces significantly under pseudorandom restrictions. In addition, we achieve nearly optimal seed-length $ildeO(log(n/epsilon))$ for the classes of: (1) read-once polynomials on $n$ variables, (2) locally-monotone ROBPs of length $n$ and width $3$ (generalizing read-once CNFs and DNFs), and (3) constant-width ROBPs of length $n$ having a layer of width $2$ in every consecutive $mathrmpolylog(n)$ layers.

Recommendations

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

Cited in

(26)

• Concentration for limited independence via inequalities for the elementary symmetric polynomials
• Fourier bounds and pseudorandom generators for product tests
• Paradigms for Unconditional Pseudorandom Generators
• Pseudorandom Bits for Oblivious Branching Programs
• scientific article; zbMATH DE number 7561753 (Why is no real title available?)
• Pseudorandomness and Fourier growth bounds for width-3 branching programs
• Hitting sets with near-optimal error for read-once branching programs
• Pseudorandomness for width-2 branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Simple optimal hitting sets for small-success RL
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• scientific article; zbMATH DE number 7561738 (Why is no real title available?)
• scientific article; zbMATH DE number 7528580 (Why is no real title available?)
• Non-malleable extractors and non-malleable codes: partially optimal constructions
• Pseudorandom generators for regular branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• scientific article; zbMATH DE number 7561734 (Why is no real title available?)
• Approximating iterated multiplication of stochastic matrices in small space
• Near-optimal derandomization of medium-width branching programs
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• A polynomial-time construction of a hitting set for read-once branching programs of width 3

This page was built for publication: Pseudorandom generators for width-3 branching programs

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