Premium
Randomness‐optimal oblivious sampling
Author(s) -
Zuckerman David
Publication year - 1997
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199712)11:4<345::aid-rsa4>3.0.co;2-z
Subject(s) - randomness , extractor , constant (computer programming) , mathematical proof , struct , constructive , mathematics , entropy (arrow of time) , discrete mathematics , binary logarithm , random function , combinatorics , computer science , algorithm , random variable , statistics , physics , geometry , process (computing) , quantum mechanics , process engineering , engineering , programming language , operating system
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 uses (1+α)( m +log γ −1 ) random bits to output d =poly(ϵ −1 , log γ −1 , m ) sample points z 1 ,…, z d ∈{0, 1} m such that for any function f : {0, 1} m →[0, 1], Pr [|(1/ d )∑ i =1 d f ( z i )− E f |≤ϵ]≥1−γ. 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 proofs. © 1997 John Wiley & Sons, Inc. Random Struct. Alg. , 11 , 345–367 (1997)