On recycling the randomness of states in space bounded computation

DOI10.1145/301250.301294zbMath1345.68135MaRDI QIDQ2819543

Omer Reingold, Ran Raz

Publication date: 29 September 2016

Published in: Proceedings of the thirty-first annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/301250.301294

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

65C10: Random number generation in numerical analysis

94A17: Measures of information, entropy

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

On the distribution of the number of roots of polynomials and explicit weak designs, Pseudorandomness via the Discrete Fourier Transform, Unnamed Item, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Preserving Randomness for Adaptive Algorithms, Optimal $\varepsilon$-Biased Sets with Just a Little Randomness, Extracting all the randomness and reducing the error in Trevisan's extractors, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, Improved Explicit Hitting-Sets for ROABPs, Pseudorandom generators for combinatorial checkerboards, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Non-interactive timestamping in the bounded-storage model, Storing information with extractors., Security analysis of NIST CTR-DRBG, No time to hash: on super-efficient entropy accumulation, Big-Key Symmetric Encryption: Resisting Key Exfiltration, On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape