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 $\hat{I}´<\epsilon$ and any co…