Pseudorandomness for width-2 branching programs

DOI10.4086/TOC.2013.V009A007MaRDI QIDQ3191575zbMATH OpenOpenAlexFDO

Authors

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4086/toc.2013.v009a007

zbMATH Keywords

branching programsharmonic analysispseudorandomness

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Randomized algorithms (68W20)

Recommendations

• Pseudorandom generators for width-3 branching programs
• Pseudorandom generators for regular branching programs
• 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

Cites work

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited in

(20)

• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
• Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Small Sample Spaces Cannot Fool Low Degree Polynomials
• Pseudorandom generators for combinatorial checkerboards
• Pseudorandom Bits for Oblivious Branching Programs
• Near-optimal pseudorandom generators for constant-depth read-once formulas
• Hitting sets give two-sided derandomization of small space
• Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
• Simple optimal hitting sets for small-success RL
• Improved pseudorandomness for unordered branching programs through local monotonicity
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• 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
• Pseudorandomness, symmetry, smoothing: I
• Pseudodistributions that beat all pseudorandom generators
• Implications of better PRGs for permutation branching programs
• On sums of INW pseudorandom generators

This page was built for publication: Pseudorandomness for width-2 branching programs

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