Browsing by Author "David Zucherman"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Computing with Very Weak Random Sources
    (1996-04-01T00:00:00Z) Aravind Srinivasan; David Zucherman
    We study how to run randomized algorithms when the source of randomness is very defective (weak). For any fixed epsilon > 0, we show how to simulate RP algorithms in time n^{O(log n)} using the output of a delta-source with min-entropy R^{epsilon}. Such a weak random source is asked once for R bits; it outputs an R-bit string according to any probability distribution that places probability at most 2^{-R^{epsilon}} on each string. If epsilon > 1/2, our simulation also works for BPP; for epsilon > 1-1/(k+1), our simulation takes time n^{O(logk n)} (logk is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R^{Omega(1)}, which is optimal. We present applications to time-space tradeoffs, expander constructions, and to the hardness of approximation. Of independent interest is our randomness-efficient Leftover Hash Lemma. This also helps us build on the work of Nisan & Zuckerman in adding a small number t of truly random bits to a weak random source to extract quasi-random bits; for delta = o(1) we make t much smaller than does the work of Nisan & Zuckerman. Aravind Srinivasan is with the Dept. of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of Singapore. His work done in parts at the National University of Singapore, at the Institute for Advanced Study, Princeton, NJ, USA (supported in part by grant 93-6-6 of the Alfred P. Sloan Foundation), and at the DIMACS Center, Rutgers University, Piscataway, NJ, USA (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology). E-mail: aravind@iscs.nus.sg. David Zuckerman is with the Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA. Part of his work was supported by NSF NYI Grant No. CCR-9457799. Part of this work was done while this author was visiting The Hebrew University of Jerusalem, supported by a Lady Davis Postdoctoral Fellowship. E-mail: diz@cs.utexas.edu. Part of this work was done while the authors attended the workshop on ``Probability and Algorithms" organized by Joel Spencer and Michael Steele, which was held at the Institute for Mathematics and its Applications at the University of Minnesota from September 20th-24th, 1993. A preliminary version of this work appears in the "Proc. IEEE Symposium on Foundations of Computer Science", pages 264-275, 1994.