TR24-097 Authors: Zhiyang Xun, David Zuckerman

Publication: 31st May 2024 20:37

Downloads: 215

Keywords:

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity for natural parameter choices. Specifically, for any constant $\alpha > 0$, for $\delta > 2^{-\mathrm{poly}(1 / \varepsilon)}$, it uses $m + O(\log (1 / \delta))$ random bits to output $t = O(\log(1 / \delta) / \varepsilon^{2 + \alpha})$ samples $Z_1, \dots Z_t \in \{0, 1\}^m$ such that for any function $f: \{0, 1\}^m \to [0, 1]$, \[

\Pr\left[\left|\frac{1}{t}\sum_{i=1}^tf(Z_i) - \mathbb{E} \, f\right| \le \varepsilon \right] \ge 1 - \delta.

\]

The sample complexity is optimal up to the $O(\varepsilon^\alpha)$ factor.

We use known connections with randomness extractors and list-decodable codes to give applications to these objects.