Bounded Independence Plus Noise Fools Products
From MaRDI portal
Publication:4641587
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
noiseReed-Solomon codespseudorandom generators\(k\)-wise independencecombinatorial rectanglessmall-bias distributions
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
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 0 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
