Typically-correct derandomization for small time and space
From MaRDI portal
Publication:5091759
Recommendations
Cites work
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
- \(\text{RL}\subseteq \text{SC}\)
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- A Chernoff Bound for Random Walks on Expander Graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Derandomizing isolation in space-bounded settings
- Exposure-resilient extractors and the derandomization of probabilistic sublinear time
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- Holographic Proofs and Derandomization
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 1250549 (Why is no real title available?)
- scientific article; zbMATH DE number 1301964 (Why is no real title available?)
- scientific article; zbMATH DE number 1097580 (Why is no real title available?)
- scientific article; zbMATH DE number 2019636 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Linear Advice for Randomized Logarithmic Space
- Making Nondeterminism Unambiguous
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- On read-once vs. multiple access to randomness in logspace
- On the distribution of the number of roots of polynomials and explicit weak designs
- On uniformity and circuit lower bounds
- Pseudorandom generators for space-bounded computation
- Pseudorandom generators without the XOR lemma
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Pseudorandomness
- Randomness is linear in space
- Simple extractors for all min-entropies and a new pseudorandom generator
- Space-bounded reducibility among combinatorial problems
- Time-space trade-off lower bounds for randomized computation of decision problems
- Time-space tradeoff in derandomizing probabilistic logspace
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma
Cited in
(3)
This page was built for publication: Typically-correct derandomization for small time and space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091759)
