Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
From MaRDI portal
Publication:5856147
DOI10.1137/17M1145707OpenAlexW3133491280MaRDI QIDQ5856147
Publication date: 24 March 2021
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1145707
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Cites Work
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- A measure of relativized space which is faithful with respect to depth
- Pseudorandom generators for space-bounded computation
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- Hardness vs randomness
- Randomness vs time: Derandomization under a uniform assumption
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Time-space tradeoff in derandomizing probabilistic logspace
- Pseudorandomness for network algorithms
- On recycling the randomness of states in space bounded computation
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- In a World of P=BPP
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Relativization of questions about log space computability
- A Pseudorandom Generator from any One-way Function
- Pseudodeterministic constructions in subexponential time
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
