Approximating iterated multiplication of stochastic matrices in small space
From MaRDI portal
Publication:6499214
DOI10.1145/3564246.3585181MaRDI QIDQ6499214
Gil Cohen, Dean Doron, Ori Sberlo, Amnon Ta-Shma
Publication date: 8 May 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On tape-bounded probabilistic Turing machine acceptors
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- Randomness is linear in space
- Relationships between nondeterministic and deterministic tape complexities
- Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Pseudorandomness for Regular Branching Programs via Fourier Analysis
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Pseudorandom Generators for Regular Branching Programs
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Computational Complexity of Probabilistic Turing Machines
- Preserving Randomness for Adaptive Algorithms
- Pseudorandom generators for width-3 branching programs
- Computational Complexity
- Pseudorandom generators for group products
- Inverting well conditioned matrices in quantum logspace
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- Computational Complexity
- Pseudorandom Generators for Read-Once Monotone Branching Programs
- Error reduction for weighted PRGs against read once branching programs
- Pseudodistributions that beat all pseudorandom generators (extended abstract)
This page was built for publication: Approximating iterated multiplication of stochastic matrices in small space
