Consider a full-rank lattice in $\mathbb{R}^n$. Let $\lambda_1$ be the length of the shortest nonzero vector. Given a vector in $\mathbb{R}^n$ we wish to find the nearest lattice vector, as measured by Euclidean distance. In general this is NP-hard. However, we can add the promise that distance to the nearest lattice vector is at most $d$. I'll refer to this as the bounded distance decoding problem. My understanding is that Babai's nearest plane algorithm provably solves this for $d \leq 2^{-c n} \lambda_1$ for some specific value of $c$ (which I don't know but which I believe to be known, and which I think maybe originates from an LLL preprocessing step). My question is whether there is a known way to efficiently go beyond this by a polynomial factor. For example, is there a known polynomial-time algorithm to solve bounded distance decoding at $d = n 2^{-cn} \lambda_1$? The closest to this that I have managed to find in the literature is an algorithm by Klein and subsequent extension by Liu, Ling, and Stehle, which appears to extend beyond the radius of Babai's algorithm by a factor of $k$ at a complexity cost of $n^{k^2}$.
Bounded distance decoding beyond Babai
polynomial time;lattice