Discrete Gaussian Sampling
Sample lattice vectors according to a discrete Gaussian.
9 variants · 12 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
DGSArbitrary width · worst caseClassical · ProvableCentered DGS on arbitrary Euclidean lattices; any positive widthWorst case30.292 DGSClassical · centered · arbitrary width · inverse-polynomial errorClassical · ProvableOne centered sample; (1+1/f(n),2^{-f(n)}) accuracy for polynomial fWorst case20.413 DGSAbove smoothing · batch samplingClassical · ProvableDGS above the lattice smoothing parameter; output 2^{n/2} samplesWorst case10.5 DGSClassical · q-ary supplied basis · onlineClassical · ProvableShifted DGS over integral q-ary lattices with integral shiftWorst case1— DGSClassical · shifted · above smoothing · 2^{0.2075n} batchClassical · ProvableJointly independent shifted-Gaussian approximation; s >= 3 eta_{1/2}(L)/2Worst case10.292481 DGSClassical · shifted · above smoothing · one sampleClassical · ProvableOne shifted sample at s >= alpha eta_{1/2}(L), fixed alpha > 1Worst case10.292481 DGSClassical · shifted · distance-relative widthClassical · ProvableShifted Gaussian samples with width above dist(t,L)/f(n)Worst case11 DGSClassical · supplied basis · Gram–Schmidt widthClassical · ProvableShifted discrete Gaussian sampling above a supplied-basis widthWorst case1— DGSClassical · supplied basis · parallel onlineClassical · ProvableShifted DGS with width controlled by the basis operator normWorst case1—