Gaussian difference dynamics breaks 2^{n/2} barrier for shortest vector problem
Original title: Gaussian Difference Dynamics: Breaking the $2^{n/2}$ Barrier for the Shortest Vector Problem and Discrete Gaussian Sampling
New algorithm solves discrete Gaussian sampling and shortest vector problem in (3/2)^{n/2+o(n)} time and (4/3)^{n/2+o(n)} space.
Classical randomized algorithms break the 2^{n/2} barrier for discrete Gaussian sampling and shortest vector problem using Gaussian difference dynamics. The framework tracks expected counts and pairwise clustering through repeated differencing. It achieves matching sieving exponents and enables batch sampling.
- Time: (3/2)^{n/2+o(n)} for DGS, 2^{0.4130n+o(n)} for SVP
- Space: (4/3)^{n/2+o(n)} for DGS, 2^{0.3138n+o(n)} for SVP
- Answers question on centered DGS
- Uses thin spherical shells for transitions
- Products
- lattices
From the original article
1 min read at arxiv.orgWe give classical randomized algorithms in a word RAM model that break the $2^{n/2}$ barrier for both discrete Gaussian sampling (DGS) and the Shortest Vector Problem (SVP). For every fixed $α>1$, shifted DGS on arbitrary lattices at width $σ\geαη_{1/2}(L)$ takes $$ (3/2)^{n/2+o(n)}\text{ time} \qquad\text{and}\qquad (4/3)^{n/2+o(n)}\text{ space}.
By Yiming Gao · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.