A Pseudorandom Oracle Characterization of ${\text{BPP}}$

DOI10.1137/0222065zbMath0782.68047OpenAlexW2164203102MaRDI QIDQ3142596

Jack H. Lutz

Publication date: 13 March 1994

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

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

zbMATH Keywords

pseudorandom generatorsrandom oraclesBPPprobabilistic complexitypseudorandom oracleresource-bounded

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On independent random oracles, Circuit size relative to pseudorandom oracles, On pseudorandomness and resource-bounded measure, Dimension extractors and optimal decompression