zbMATH — the first resource for mathematics

Randomness-optimal oblivious sampling. (English) Zbl 0891.60100
Summary: 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 \(\alpha> 0\), it uses \((1+\alpha) (m+\log \gamma^{-1})\) random bits to output \(d= \text{poly} (\varepsilon^{-1}, \log \gamma^{-1}, m)\) sample points \(z_1, \dots, z_d\in \{0,1\}^m\) such that for any function \(f:\{0,1\}^m \to[0,1]\), \({\mathbf Pr} [|(1/d) \sum^d_{i=1} f(z_i)- {\mathbf E} f|\leq \varepsilon] \geq 1-\gamma\). 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.

60K99 Special processes
68P10 Searching and sorting
90B40 Search theory
Full Text: DOI