Lower space bounds for randomized computation
From MaRDI portal
Publication:4632458
DOI10.1007/3-540-58201-0_100zbMath1418.68094OpenAlexW2091845976MaRDI QIDQ4632458
Marek Karpinski, Rūsiņš Freivalds
Publication date: 29 April 2019
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/3-540-58201-0_100
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Affine automata verifiers ⋮ Language recognition power and succinctness of affine automata ⋮ Lower time bounds for randomized computation ⋮ Unbounded-error quantum computation with small space bounds ⋮ Probabilistic rebound Turing machines ⋮ Multihead two-way probabilistic finite automata ⋮ Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice
Cites Work
- A lower bound for probabilistic algorithms for finite state machines
- On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
- Non-negative matrices and Markov chains. 2nd ed
- An introduction to randomized algorithms
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Computational Complexity of Probabilistic Turing Machines
- Finite state verifiers I
- On randomized versus deterministic computation
- Estimating a probability using finite memory
- Probabilistic automata
- A context-free language which is not acceptable by a probabilistic automaton
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
