On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
From MaRDI portal
Publication:2946415
DOI10.1007/978-3-662-48054-0_38zbMath1465.68073MaRDI QIDQ2946415
A. Pavan, Debasis Mandal, N. V. Vinodchandran
Publication date: 16 September 2015
Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_38
68Q25: Analysis of algorithms and problem complexity
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68W20: Randomized algorithms
68Q04: Classical models of computation (Turing machines, etc.)
Cites Work
- Pseudorandom generators for space-bounded computation
- On read-once vs. multiple access to randomness in logspace
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
- How strong is Nisan's pseudo-random generator?
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- S-T connectivity on digraphs with a known stationary distribution
- Undirected connectivity in log-space
- 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
- On Time Versus Space
- Computational Complexity of Probabilistic Turing Machines
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Computational Complexity
- Linear Advice for Randomized Logarithmic Space
- Holographic Proofs and Derandomization
- Fundamentals of Computation Theory
