Pseudorandomness and Fourier growth bounds for width-3 branching programs

DOI10.4230/LIPICS.APPROX-RANDOM.2014.885MaRDI QIDQ2969669zbMATH OpenFDO

Authors Thomas Steinke, Andrew Wan, Salil Vadhan

Publication date 22 March 2017

zbMATH Keywords

pseudorandomnessbranching programsdiscrete Fourier analysis

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

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

Cited in

(9)

• Fourier bounds and pseudorandom generators for product tests
• Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
• Pseudorandom generators for width-3 branching programs
• Pseudorandomness for width-2 branching programs
• Pseudorandomness and Fourier-growth bounds for width-3 branching programs
• Pseudorandomness for regular branching programs via Fourier analysis
• Pseudorandom generators for regular branching programs
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Bounded independence plus noise fools products

This page was built for publication: Pseudorandomness and Fourier growth bounds for width-3 branching programs

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