\(\text{RL}\subseteq \text{SC}\)
From MaRDI portal
Publication:1327590
DOI10.1007/BF01205052zbMath0806.68043OpenAlexW2337498233WikidataQ56452238 ScholiaQ56452238MaRDI QIDQ1327590
Publication date: 19 June 1994
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01205052
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Connectivity (05C40) Randomized algorithms (68W20)
Related Items (18)
Pseudorandomness via the Discrete Fourier Transform ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Unnamed Item ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Deterministic parallel algorithms for bilinear objective functions ⋮ On the computational complexity of the Riemann mapping ⋮ Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space ⋮ Arithmetizing classes around {\textsf{NC}}\(^{1}\) and {\textsf{L}} ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Bravely, Moderately: A Common Theme in Four Recent Works ⋮ Typically-correct derandomization for small time and space ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
Cites Work
This page was built for publication: \(\text{RL}\subseteq \text{SC}\)
