# 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 < ||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?

• I notice that you've asked the same question on MO: mathoverflow.net/questions/37563/… While crossposting is fine in general, it would be helpful to post on one site and wait for a bit before crossposting, especially since it appears that you've got your answer already on MO. Also see meta.cstheory.stackexchange.com/questions/25/… – Suresh Venkat Sep 3 '10 at 3:04
• Sorry about this, was a little eager to hear the answer, so I thought I would maximize my chances and cross post. I'll make sure to give a little time between cross posting next time. – user834 Sep 3 '10 at 5:52
• Answered on mathoverflow: mathoverflow.net/questions/37563/… . I'll keep it here in the hopes of getting more answers. – user834 Sep 4 '10 at 11:42

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.
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.