Pseudorandom number generation and space complexity

DOI10.1016/S0019-9958(85)80043-7MaRDI QIDQ3694692zbMATH OpenFDO

Authors Merrick Furst, Richard J. Lipton, Larry J. Stockmeyer

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(85)80043-7

zbMATH Keywords

bipartite graphdeterministic simulationdiscrete logarithm problemintractabilitymatchingpolynomial time probabilistic Turing machinespace complexity

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random number generation in numerical analysis (65C10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(2)

• Hardness vs randomness
• Pseudorandom bits for constant depth circuits

This page was built for publication: Pseudorandom number generation and space complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3694692)