Simulating BPP Using a General Weak Random Source

It is shown how to simulate BPP and approximation algorithms in polynomial time using the output from a delta -source. A delta -source is a weak random source that is asked only once for R bits, and must output an R-bit string according to some distribution that places probability no more than 2/sup - delta R/ on any particular string. Also given are two applications: one to show the difficulty of approximating the size of the maximum clique, and the other to the problem of implicit O(1) probe search. >

Authors

• David Zuckerman

Keywords

• Polynomials
• Computer science
• Approximation algorithms
• Application software
• Probes
• Physics computing
• Diodes
• Clocks
• History
• Entropy
• Source Of Randomness
• Permutation
• High Probability
• Polydispersity Index
• Loss Of Generality
• Estimation Algorithm
• Family Functioning
• Rainbow
• Block Size
• Hash Function
• Block Length
• Brute Force
• Polynomial-time Algorithm
• Finite Field
• Power-of-two
• Non-zero Probability
• Algorithm Works
• Construction Of Solutions
• Rest Of The Proof