Pseudorandom Bits for Oblivious Branching Programs

DOI10.1145/3378663MaRDI QIDQ5053059zbMATH OpenOpenAlexFDO

Authors Rohit Gurjar, Ben Lee Volk

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

oblivious branching programspseudorandom generator

Mathematics Subject Classification ID

Data structures (68P05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polynomial width branching programs, the seed lengths in our constructions are $ildeO(n^{1-1/2^{k-1}})$ (for the read-$k$ case) and $O(n/loglogn)$ (for the linear length case). Previously, the best construction for these models required seed length $(1-Omega(1))n$.

Recommendations

• Pseudorandomness for width-2 branching programs
• Pseudorandom generators for regular branching programs
• The power of nondeterminism and randomness for oblivious branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandom generators for width-3 branching programs
• Pseudorandom bits and lower bounds for randomized Turing machines
• Improved pseudorandomness for unordered branching programs through local monotonicity

Cited in

(12)

• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Pseudorandomness for regular branching programs via Fourier analysis
• 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 for width-2 branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Pseudorandom generators for width-3 branching programs
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Pseudorandom Generators for Read-Once Monotone Branching Programs
• Lower bounds for set-multilinear branching programs

This page was built for publication: Pseudorandom Bits for Oblivious Branching Programs

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