In a World of P=BPP
From MaRDI portal
Publication:3088186
DOI10.1007/978-3-642-22670-0_20zbMath1343.68084OpenAlexW2131757234MaRDI QIDQ3088186
Publication date: 19 August 2011
Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_20
derandomizationpseudorandom generatorssearch problemsFPTASpromise problemsBPPrandomized constructions
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
Quantified Derandomization: How to Find Water in the Ocean, Pseudorandom generators for combinatorial checkerboards, Two Comments on Targeted Canonical Derandomizers, Paradigms for Unconditional Pseudorandom Generators, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, On the de-randomization of space-bounded approximate counting problems
Cites Work
- Unnamed Item
- Unnamed Item
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- Probabilistic encryption
- Random generation of combinatorial structures from a uniform distribution
- On the power of two-point based sampling
- Hardness vs randomness
- Randomness vs time: Derandomization under a uniform assumption
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Pseudorandomness and average-case complexity via uniform reductions
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Low-End Uniform Hardness versus Randomness Tradeoffs for AM
- A proof of alon's second eigenvalue conjecture
- The complexity of promise problems with applications to public-key cryptography
- Complexity Measures for Public-Key Cryptosystems
- Foundations of Cryptography
- An Unconditional Study of Computational Zero Knowledge
- Computational Complexity
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- On the difference between consecutive primes
