On using deterministic functions to reduce randomness in probabilistic algorithms
We show the existence of nonuniform schemes for the following sampling problem: Given a sample space with n points, an unknown set of size n/2, and s random points, it is possible to generate deterministically from them \(s+k\) points such that the probability of not hitting the unknown set is exponentially smaller in k than \(2^{-s}\). Tight bounds are given for the quality of such schemes. Explicit, uniform versions of these schemes could be used for efficiently reducing the error probability of randomized algorithms. A survey of known constructions (whose quality is very far from the existential result) is included.
- Algorithmic randomness of continuous functions
- Simple and fast derandomization from very hard functions: eliminating randomness at almost no cost
- Probabilistic Algorithmic Randomness
- A relation between correctness and randomness in the computation of probabilistic algorithms
- Algorithmic Randomness
- On randomized versus deterministic computation
- On randomized versus deterministic computation
- Deterministic approximations of probability inequalities
- Using nondeterminism to design efficient deterministic algorithms
- A Remark on Stirling's Formula
- A Simple Unpredictable Pseudo-Random Number Generator
- Better expanders and superconcentrators
- Expanders obtained from affine transformations
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking Networks
- Superconcentrators
- On the power of two-point based sampling
- Pseudorandom generators for space-bounded computation
- Randomness in interactive proofs
- A simple analysis of the error probability of two-point based sampling
- On the second eigenvalue of hypergraphs
- Simulating BPP using a general weak random source
- Realistic analysis of some randomized algorithms
- Logarithmic reduction of the level of randomness in some probabilistic geometric constructions
- Extractors from Reed-Muller codes
- scientific article; zbMATH DE number 1301095 (Why is no real title available?)
- Construction of expanders and superconcentrators using Kolmogorov complexity
- Using Rademacher permutations to reduce randomness
This page was built for publication: On using deterministic functions to reduce randomness in probabilistic algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094137)
