Generating quasi-random sequences from semi-random sources
From MaRDI portal
Publication:1088641
DOI10.1016/0022-0000(86)90044-9zbMath0612.94004OpenAlexW1977568210MaRDI QIDQ1088641
Umesh V. Vazirani, Miklos Santha
Publication date: 1986
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(86)90044-9
Related Items (46)
Collapse of PP with a semi-random source to BPP ⋮ Limits on the usefulness of random oracles ⋮ Smoothed analysis of binary search trees ⋮ Randomness Tests: Theory and Practice ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources ⋮ Extractors for weak random sources and their applications ⋮ Privacy with Imperfect Randomness ⋮ Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Deterministic extractors for affine sources over large fields ⋮ The entropy of a distributed computation random number generation from memory interleaving ⋮ Biased random walks ⋮ Efficient learning of typical finite automata from random walks ⋮ Simulating BPP using a general weak random source ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ On the impossibility of cryptography with tamperable randomness ⋮ Deterministic Randomness Extraction from Generalized and Distributed Santha--Vazirani Sources ⋮ On secret sharing, randomness, and random-less reductions for secret sharing ⋮ Santha-Vazirani sources, deterministic condensers and very strong extractors ⋮ Semi-device-independent randomness expansion using \(n\rightarrow1\) sequential quantum random access codes ⋮ A comprehensive review of quantum random number generators: concepts, classification and the origin of randomness ⋮ Average case analysis of fully dynamic connectivity for directed graphs ⋮ Learning under \(p\)-tampering poisoning attacks ⋮ Unnamed Item ⋮ How to get more mileage from randomness extractors ⋮ Some extremal problems arising from discrete control processes ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Deterministic extractors for small-space sources ⋮ Improved Extractors for Recognizable and Algebraic Sources ⋮ Cryptanalytic Attacks on Pseudorandom Number Generators ⋮ An Introduction to Randomness Extractors ⋮ Coloring random graphs ⋮ Proved Random Numbers Obtained from Hardware Devices ⋮ Improving the Hadamard extractor ⋮ Extractors from Reed-Muller codes ⋮ Secrecy Without Perfect Randomness: Cryptography with (Bounded) Weak Sources ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ Bounds on Fixed Input/Output Length Post-processing Functions for Biased Physical Random Number Generators ⋮ Explicit two-source extractors and resilient functions ⋮ Increasing the output length of zero-error dispersers ⋮ Average case analysis of fully dynamic reachability for directed graphs ⋮ Extracting randomness: A survey and new constructions ⋮ A note on the influence of an \(\epsilon\)-biased random source ⋮ Universal tests for nonuniform distributions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization by Simulated Annealing
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Probabilistic algorithm for testing primality
- Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- The Wire-Tap Channel
- A Fast Monte-Carlo Test for Primality
- A General Approach for Generating Natural Random Variables
- Class of constructive asymptotically good algebraic codes
This page was built for publication: Generating quasi-random sequences from semi-random sources
