Bounded Independence Plus Noise Fools Products

DOI10.1137/17M1129088zbMath1441.94114OpenAlexW2796642617WikidataQ130037534 ScholiaQ130037534MaRDI QIDQ4641587

Elad Haramaty, Emanuele Viola, Chin Ho Lee

Publication date: 18 May 2018

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

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

zbMATH Keywords

noiseReed-Solomon codespseudorandom generators\(k\)-wise independencecombinatorial rectanglessmall-bias distributions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Pseudo-random numbers; Monte Carlo methods (11K45) Synchronization error-correcting codes (94B50)

Related Items (5)

Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudorandom generators for combinatorial checkerboards
• Randomness buys depth for approximate counting
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Constructions of low-degree and error-correcting \(\varepsilon \)-biased generators
• A note on the decoding complexity of error-correcting codes
• Almost \(k\)-wise independence versus \(k\)-wise independence
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• On the power of two-point based sampling
• Pseudorandom generators for space-bounded computation
• Universal classes of hash functions
• Improved algorithms via approximations of probability distributions
• Improved pseudorandom generators for combinatorial rectangles
• Randomness is linear in space
• Pseudorandomness for network algorithms
• Pseudorandom Generators for Combinatorial Shapes
• Pseudorandomness for Regular Branching Programs via Fourier Analysis
• The Complexity of Distributions
• Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
• A Simple Proof of Bazzi’s Theorem
• Pseudorandom Bits for Polynomials
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Pseudorandomness for Linear Length Branching Programs and Stack Machines
• Parity, circuits, and the polynomial-time hierarchy
• Endcoding Complexity Versus Minimum Distance
• Polylogarithmic independence fools AC ⁰ circuits
• Polylogarithmic Independence Can Fool DNF Formulas
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Simple Constructions of Almost k-wise Independent Random Variables
• Pseudorandomness via the Discrete Fourier Transform
• Efficient approximation of product distributions
• On the Correlation of Parity and Small-Depth Circuits
• Pseudorandomness from Shrinkage
• Bounded Independence Fools Halfspaces
• Pseudorandomness for Read-Once Formulas

This page was built for publication: Bounded Independence Plus Noise Fools Products