Discrete Gaussian sampling in 2^{n/2+o(n)} time, apparently one sample at a time now.
2 comments
“one sample at a time” is the wrong yardstick here, because in the lattice setting you usually care about a stream of samples with controlled state and amortized cost, not a heroic one-shot. If this is really 2^{n/2+o(n)} per sample, that does not buy you much for any protocol I’d actually build (and it says nothing about what happens when you need the same gadget 1000 times....)
> a stream of samples with controlled state and amortized cost
That part matters a lot here, because many lattice samplers hide work in preprocessing or a retained basis, so the real comparison is often per sample after the first few outputs.
A 2^{n/2+o(n)} one-shot bound is still a nice complexity result, but it leaves open whether the same setup keeps giving independent samples without the memory or state cost getting ugly.