Pseudorandom sources for BPP

DOI10.1016/0022-0000(90)90023-EzbMath0721.68024MaRDI QIDQ2641105

Jack H. Lutz

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

pseudorandomnessresource-bounded measureprobabilistic machine

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Normal numbers and sources for BPP, Random languages for nonuniform complexity classes, On independent random oracles, Almost everywhere high nonuniform complexity, Circuit size relative to pseudorandom oracles

Cites Work

• Unnamed Item
• Unnamed Item
• On the notion of infinite pseudorandom sequences
• One way functions and pseudorandom generators
• Families of recursive predicates of measure zero
• On Deviations of the Sample Mean
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Computational Complexity of Probabilistic Turing Machines
• The definition of random sequences
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations