Other norms for Lattice reduction techniques (LLL, PSLQ)?

Question

LLL and other lattice reduction techniques (such as PSLQ) try to find a short basis vector relative to the 2-norm, i.e. for a given basis that has $ \varepsilon $ as its shortest vector, $ \varepsilon \in Z^n $, find a short vector s.t. $ b \in Z^n, ||b||_2 < ||c^n \varepsilon||_2 $.

Has there been any work done to find short vectors based on other, potentially higher, norms? Is this a meaningful question?

Answer 1

Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper

• Oded Regev and Ricky Rosen. Lattice problems and norm embeddings, STOC 2006. doi: 10.1145/1132516.1132581 (full preprint version)

This paper presents randomized reductions from the approximation versions of lattice problems in the $\ell_2$ norm to any norm $\ell_p$ where $1 \le p \le \infty$. The reductions don't quite preserve the approximation ratio, but the loss can be bounded by a factor of $(1+\epsilon)$. So the $\ell_2$ norm yields in some sense the "easiest" versions of lattice problems. It is enough to prove hardness of approximation using the $\ell_2$ norm, and hardness of approximation for any other $\ell_p$ norm follows with only a $(1+\epsilon)$ larger approximation factor.

Regev and Rosen then go on to use this to strengthen some existing hardness results.

On the other hand, Chris Peikert showed that lattice problems posed using $\ell_p$ norms are not substantially harder than problems posed in the $\ell_2$ norm.

• Chris Peikert, Limits on the hardness of lattice problems in $\ell_p$ norms, Computational Complexity 17 300–351, 2008. doi: 10.1007/s00037-008-0251-3 (full preprint version)

So yes, the question is sensible, and it has also essentially been answered.

(Thanks to @user834 for the preprint links.)