Other norms for Lattice reduction techniques (LLL, PSLQ)? 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 &lt; ||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?
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.)