Pseudorandomness via the Discrete Fourier Transform
From MaRDI portal
Publication:4562280
DOI10.1137/16M1062132zbMath1410.65007arXiv1506.04350OpenAlexW2904894749MaRDI QIDQ4562280
Raghu Meka, Daniel M. Kane, Parikshit Gopalan
Publication date: 19 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.04350
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Random number generation in numerical analysis (65C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Fooling Polytopes, Polynomial Data Structure Lower Bounds in the Group Model, Unnamed Item, Paradigms for Unconditional Pseudorandom Generators, Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time, Bounded Independence Plus Noise Fools Products, Simple and efficient pseudorandom generators from gaussian processes, Fourier bounds and pseudorandom generators for product tests, Unnamed Item, Perfect $L_p$ Sampling in a Data Stream
Cites Work
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- Improved pseudorandom generators for combinatorial rectangles
- Randomness is linear in space
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Balls and Bins: Smaller Hash Families and Faster Evaluation
- Pseudorandom Generators for Combinatorial Shapes
- Pseudorandom Generators for Polynomial Threshold Functions
- Explicit Dimension Reduction and Its Applications
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Almost Optimal Pseudorandom Generators for Spherical Caps
- Almost Optimal Explicit Johnson-Lindenstrauss Families
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Pseudorandom Generators for Regular Branching Programs
- Undirected connectivity in log-space
- Pseudorandom Bit Generators That Fool Modular Sums
- Small-Bias Spaces for Group Products
- Efficient approximation of product distributions
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Probability Inequalities for Sums of Bounded Random Variables
- Bounded Independence Fools Halfspaces
- Explicit Construction of a Small $\epsilon$-Net for Linear Threshold Functions
- An invariance principle for polytopes
- Pseudorandom generators for group products
- A Small PRG for Polynomial Threshold Functions of Gaussians
