On read-once vs. multiple access to randomness in logspace
From MaRDI portal
(Redirected from Publication:1208412)
Recommendations
Cites work
- Computational Complexity of Probabilistic Turing Machines
- Nondeterministic Space is Closed under Complementation
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Space-bounded hierarchies and probabilistic computations
- There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
- Two Applications of Inductive Counting for Complementation Problems
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
- scientific article; zbMATH DE number 7561738 (Why is no real title available?)
- 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)
