Randomness-optimal oblivious sampling

✍ Scribed by David Zuckerman

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 246 KB
• Volume: 11
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199712)11:4<345::aid-rsa4>3.0.co;2-z

✦ Synopsis

We present the first efficient oblivious sampler that uses an optimal number of random bits, up to an arbitrary constant factor bigger than 1. Specifically, for any ␣ ) 0, it Ž .Ž y 1 . Ž y 1 y 1

. uses 1 q ␣ m q log ␥ random bits to output ds poly ⑀ , log ␥ , m sample points Ä 4 m Ä 4 m w x w<Ž . d Ž . < z , . . . , z g 0, 1 such that for any function f : 0,1 ª 0, 1 ,

x ⑀ G1y␥. Our proof is based on an improved extractor construction. An extractor is a procedure which takes as input the output of a defective random source and a small number of truly random bits, and outputs a nearly random string. We present the first optimal extractor, up to constant factors, for defective random sources with constant entropy rate. We give applications to constructive leader election and reducing randomness in interactive Ž .