On Complexity of Gaussian Sampling

Huanjian Zhou, Taiji Suzuki

We study the number of exact matrix-vector queries needed to sample a centered $d$-dimensional Gaussian with condition number at most $\kappa$ to total variation error $\epsilon$. Th…