Pseudorandom generators for width-3 branching programs

DOI10.1145/3313276.3316319zbMATH Open1433.68604arXiv1806.04256OpenAlexW2963619305MaRDI QIDQ5212804FDOQ5212804

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)

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.

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

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

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)

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
• Title not available (Why is that?)
• Hitting sets with near-optimal error for read-once branching programs
• Pseudorandomness and Fourier growth bounds for width-3 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)