Typically-Correct Derandomization for Small Time and Space
Lists
Only you see this
Abstract
Suppose a language $L$ can be decided by a bounded-error randomized algorithm that runs in space $S$ and time $n \cdot \text{poly}(S)$. We give a randomized algorithm for $L$ that still runs in space $O(S)$ and time $n \cdot \text{poly}(S)$ that uses only $O(S)$ random bits; our algorithm has a low failure probability on all but a negligible fraction of inputs of each length. An immediate corollary is a deterministic algorithm for $L$ that runs in space $O(S)$ and succeeds on all but a negligible fraction of inputs of each length. We also give several other complexity-theoretic applications of our technique.
BibTeX
@inproceedings{hoza2017typically,
author = {William M. Hoza},
title = {{Typically-Correct Derandomization for Small Time and Space}},
booktitle = {CCC},
year = {2017},
doi = {10.4230/lipics.ccc.2019.9},
}| Hitting Sets Give Two-Sided Derandomization of Small Space | Theory Comput · 2022 |
| Hardness vs. randomness | [proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · 1988 |
| Pseudorandom generators for width-3 branching programs | arXiv · 2018 |
| Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions | ECCC · 2025 |
| Pseudorandomness via the Discrete Fourier Transform | arXiv · 2015 |
| Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits | arXiv · 2018 |