On read-once vs. multiple access to randomness in logspace

DOI10.1016/0304-3975(93)90258-UzbMATH Open0774.68037DBLPjournals/tcs/Nisan93OpenAlexW1981030589WikidataQ29027264 ScholiaQ29027264MaRDI QIDQ1208412FDOQ1208412

Authors: Noam Nisan 

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90258-u

Recommendations

• Multiple usage of random bits in finite automata
• On probabilistic space-bounded machines with multiple access to random tape
• A note on the advice complexity of multipass randomized logspace
• On the power of randomized multicounter machines
• Randomness is linear in space

zbMATH Keywords

randomnessmultiple accessrandomized logspace machinerandomized space-bounded computationread- once accesstwo-sided errorzero error

Mathematics Subject Classification ID

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

Cites Work

• Space-bounded hierarchies and probabilistic computations
• Nondeterministic Space is Closed under Complementation
• Computational Complexity of Probabilistic Turing Machines
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Two Applications of Inductive Counting for Complementation Problems
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator

Cited In (12)

• On probabilistic space-bounded machines with multiple access to random tape
• Pseudorandom generators for combinatorial checkerboards
• Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems
• Running time analysis of broadcast consensus protocols
• \(\text{RL}\subseteq \text{SC}\)
• Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
• A note on the advice complexity of multipass randomized logspace
• Title not available (Why is that?)
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• How strong is Nisan's pseudo-random generator?
• Multiple usage of random bits in finite automata
• Typically-correct derandomization for small time and space

This page was built for publication: On read-once vs. multiple access to randomness in logspace

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