What are the main open problems on lattice-basis reduction algorithms (such as LLL)? I am looking for problems satisfying the following two conditions:
(a) their solution would likely be of some practical utility,
(b) their statement is neat and simple. (For instance, I understand that, while the fact that LLL performs better in practice than it does in theory is interesting, important and, by definition, not fully explained, it is also difficult to phrase clearly, due to the fact that "real-world" inputs are not typical, i.e., don't tend to mimic what would seem to be a natural distribution from a mathematical perspective).
Please understand this question to cover also algorithms that find a short vector in a lattice (without finding a full basis). For example - the ratio between the shortest vector that LLL finds and the minimal vector can be as large as exponential on $n$. Finding the minimal vector is, if I understand correctly, computationally hard - but what about finding a short vector whose ratio to the minimal vector is much less than exponential? (I understand there is an algorithm that does give a ratio that is slightly less than exponential - what is it?) How interesting and how hard is this felt to be?