scientific article; zbMATH DE number 3876586

MaRDI QIDQ3341893zbMATH OpenFDO

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

Publication date 1983

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)

Recommendations

• Pseudorandom generators for space-bounded computation
• A primer on pseudorandom generators
• Hardness vs randomness
• Some consequences of the existnce of pseudorandom generators
• Efficient Parallel Pseudorandom Number Generation

Cited in

(11)

• A survey of space complexity
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• Hardness vs randomness
• On recycling the randomness of states in space bounded computation
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
• scientific article; zbMATH DE number 3954270 (Why is no real title available?)
• scientific article; zbMATH DE number 3980487 (Why is no real title available?)
• scientific article; zbMATH DE number 1301964 (Why is no real title available?)
• Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
• Pseudorandom bits and lower bounds for randomized Turing machines

This page was built for publication:

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