Dispersers, deterministic amplification, and weak random sources
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The use of highly expanding bipartite multigraphs (called dispersers) to reduce greatly the error of probabilistic algorithms at the cost of few additional random bits is treated. Explicit constructions of such graphs are generalized and used to obtain the following results: (1) The error probability of any RP (BPP) algorithm can be made exponentially small at the cost of only a constant factor increase in the number of random bits. (2) RP (BPP) algorithms with some weak bit fixing sources are simulated.<>Keywords
This publication has 15 references indexed in Scilit:
- Independent Unbiased Coin Flips From A Correlated Biased Source: A Finite State Markov ChainPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- How to recycle random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- The influence of variables on Boolean functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- New algorithms for finding irreducible polynomials over finite fieldsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Realistic analysis of some randomized algorithmsPublished by Association for Computing Machinery (ACM) ,1987
- Imperfect random sources and discrete controlled processesPublished by Association for Computing Machinery (ACM) ,1987
- Eigenvalues, geometric expanders, sorting in rounds, and ramsey theoryCombinatorica, 1986
- Expanders, randomness, or time versus spacePublished by Springer Nature ,1986
- Explicit expanders and the Ramanujan conjecturesPublished by Association for Computing Machinery (ACM) ,1986
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981