Pseudorandom generators for combinatorial shapes

DOI10.1137/110854990MaRDI QIDQ2848209zbMATH OpenOpenAlexFDO

Authors Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110854990

zbMATH Keywords

central limit theoremsderandomizationpseudorandomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Pseudorandom generators for combinatorial shapes
• Improved pseudorandom generators for combinatorial rectangles
• Pseudorandom generators for combinatorial checkerboards
• Pseudorandom Bit Generators That Fool Modular Sums
• Improved pseudorandom generators for depth 2 circuits

Cited in

(14)

• Improved pseudorandom generators for combinatorial rectangles
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• Optimal hitting sets for combinatorial shapes
• Entropy of weight distributions of small-bias spaces and pseudobinomiality
• scientific article; zbMATH DE number 3919430 (Why is no real title available?)
• Pseudorandom generators for combinatorial checkerboards
• scientific article; zbMATH DE number 1053089 (Why is no real title available?)
• Pseudorandomness via the discrete Fourier transform
• Bounded independence plus noise fools products
• Generation of Random Triangular Digital Curves Using Combinatorial Techniques
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• Pseudorandom generators for combinatorial shapes
• Randomness efficient noise stability and generalized small bias sets

This page was built for publication: Pseudorandom generators for combinatorial shapes

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