On recycling the randomness of states in space bounded computation
From MaRDI portal
Publication:2819543
DOI10.1145/301250.301294zbMath1345.68135MaRDI QIDQ2819543
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
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