On read-once vs. multiple access to randomness in logspace
From MaRDI portal
Publication:1208412
DOI10.1016/0304-3975(93)90258-UzbMath0774.68037OpenAlexW1981030589WikidataQ29027264 ScholiaQ29027264MaRDI QIDQ1208412
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
multiple accessrandomnessrandomized logspace machinerandomized space-bounded computationread- once accesstwo-sided errorzero error
Related Items
\(\text{RL}\subseteq \text{SC}\), On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape, Pseudorandom generators for combinatorial checkerboards, How strong is Nisan's pseudo-random generator?, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Running time analysis of broadcast consensus protocols, Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs, Unnamed Item, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Typically-correct derandomization for small time and space
Cites Work
- Space-bounded hierarchies and probabilistic computations
- There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Nondeterministic Space is Closed under Complementation
- Two Applications of Inductive Counting for Complementation Problems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Computational Complexity of Probabilistic Turing Machines
