\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)

DOI10.1006/jcss.1998.1616zbMath0922.68083OpenAlexW1488557728MaRDI QIDQ1288206

Michael E. Saks, Shiyu Zhou

Publication date: 11 May 1999

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1998.1616

zbMATH Keywords

pseudorandom generatorspace-bounded computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10) Randomized algorithms (68W20)

Related Items (19)

On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Pseudorandom generators, typically-correct derandomization, and circuit lower bounds ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Preserving Randomness for Adaptive Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Typically-correct derandomization for small time and space ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the power of two-point based sampling
• Symmetric space-bounded computation
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• Universal classes of hash functions
• Relationships between nondeterministic and deterministic tape complexities
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Computational Complexity of Probabilistic Turing Machines
• More deterministic simulation in logspace

This page was built for publication: \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)