Near-Optimal Averaging Samplers and Matrix Samplers

Zhiyang Xun, David Zuckerman

We present the first efficient averaging sampler that achieves asymptotically optimal randomness complexity and near-optimal sample complexity. For any $\delta <\epsilon$ and any con…