One Discrete Gaussian Sample in $2^{n/2+o(n)}$ Time

Jiseung Kim

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/…