Typically-correct derandomization for small time and space
From MaRDI portal
Publication:5091759
DOI10.4230/LIPIcs.CCC.2019.9OpenAlexW2965699952MaRDI QIDQ5091759
Publication date: 27 July 2022
Full work available at URL: https://arxiv.org/abs/1711.00565
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
- On uniformity and circuit lower bounds
- Exposure-resilient extractors and the derandomization of probabilistic sublinear time
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Pseudorandom generators for space-bounded computation
- On read-once vs. multiple access to randomness in logspace
- Space-bounded reducibility among combinatorial problems
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- \(\text{RL}\subseteq \text{SC}\)
- Hardness vs randomness
- Randomness is linear in space
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Time-space tradeoff in derandomizing probabilistic logspace
- Pseudorandomness
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Time-space trade-off lower bounds for randomized computation of decision problems
- Simple extractors for all min-entropies and a new pseudorandom generator
- A Chernoff Bound for Random Walks on Expander Graphs
- On the distribution of the number of roots of polynomials and explicit weak designs
- Making Nondeterminism Unambiguous
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Linear Advice for Randomized Logarithmic Space
- Holographic Proofs and Derandomization
- Pseudorandom generators without the XOR lemma
This page was built for publication: Typically-correct derandomization for small time and space
