Simulating BPP using a general weak random source
1991
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.<
>
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
28
References
0
Citations
NaN
KQI