Simulating BPP using a general weak random source
From MaRDI portal
Publication:1923854
DOI10.1007/BF01940870zbMath0857.68121MaRDI QIDQ1923854
Publication date: 18 February 1997
Published in: Algorithmica (Search for Journal in Brave)
Related Items
The Untold Story of $$\mathsf {SBP}$$ ⋮ A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes ⋮ Extractors for weak random sources and their applications ⋮ Privacy with Imperfect Randomness ⋮ Deterministic extractors for affine sources over large fields ⋮ \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\) ⋮ Estimating gaps in martingales and applications to coin-tossing: constructions and hardness ⋮ Efficient construction of a small hitting set for combinatorial rectangles in high dimension ⋮ On testing for zero polynomials by a set of points with bounded precision. ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ How to get more mileage from randomness extractors ⋮ Deterministic extractors for small-space sources ⋮ Distinguishing Distributions Using Chernoff Information ⋮ Pseudorandom generators without the XOR lemma ⋮ Extractors from Reed-Muller codes ⋮ On zero error algorithms having oracle access to one query ⋮ Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes ⋮ Unnamed Item ⋮ Extracting all the randomness and reducing the error in Trevisan's extractors ⋮ A unified approach to deterministic encryption: new constructions and a connection to computational entropy ⋮ Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More) ⋮ Simplified Derandomization of BPP Using a Hitting Set Generator
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-deterministic exponential time has two-prover interactive protocols
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Some extremal problems arising from discrete control processes
- Generating quasi-random sequences from semi-random sources
- On using deterministic functions to reduce randomness in probabilistic algorithms
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Expanders, randomness, or time versus space
- On the power of two-point based sampling
- Probabilistic algorithm for testing primality
- Explicit constructions of linear-sized superconcentrators
- Universal classes of hash functions
- On the power of multi-prover interactive protocols
- Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
- On the second eigenvalue of hypergraphs
- Randomness is linear in space
- Improved non-approximability results
- Explicit Concentrators from Generalized N-Gons
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Privacy Amplification by Public Discussion
- A random polynomial-time algorithm for approximating the volume of convex bodies
- Expanders that beat the eigenvalue bound
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- The Efficient Construction of an Unbiased Random Sequence
